查找列表中出现奇数次的元素

Question

假设我们需要在 O(N) 时间和 O(1) space 复杂度内找到在排序列表中出现奇数次的所有元素。

ls = [1,2,2,3,3,3,4,5,5,6,6,6,6,6]        
output = [1,3,4,6]

我们不会return一个新的列表，也许会覆盖现有的

我有一种使用哈希技术的方法，但它会导致复杂度为 O(N) space。

我尝试过使用异或进行位运算，但我无法解决问题。

Answer 1

遍历列表，计算当前项与前一项相同的情况，如果不同且计数为奇数，则向列表的开头覆盖。

此解决方案覆盖现有列表而不是分配新列表，并且具有 O(N) 时间复杂度。因为新列表会更短，所以我们必须 pop 从它的末尾开始剩余的项目。（我们通常会使用 ls = ls[position:] 进行拼接，但这会分配一个新列表，这是不允许的。）

def keep_odd_elements(ls):
    count = 0
    write_position = 0
    previous = object()
    for item in ls:
        if item == previous:
            count += 1
        else:
            # Write the odd-counted numbers towards the start of the list
            if count % 2:
                ls[write_position] = previous
                write_position += 1
            count = 1
        previous = item
    if count % 2:
        ls[write_position] = previous
        write_position += 1
    # Remove the leftover items at the end of the list
    for _ in range(write_position, len(ls)):
        ls.pop()
    
ls = [1,2,2,3,3,3,4,5,5,6,6,6,6,6]
keep_odd_elements(ls)
print(ls)   # [1, 3, 4, 6]

如果我们取消不分配新列表的要求，那么我们可以写得更优雅：

def get_odd_elements(ls):
    count = 0
    for a, b in zip([object()] + ls, ls + [object()]):
        if a == b:
            count += 1
        else:
            if count % 2:
                yield a
            count = 1

print(list(get_odd_elements([1,2,2,3,3,3,4,5,5,6,6,6,6,6])))

Answer 2

这是在 O(n) 中运行并使用 O(1) 辅助内存的 C++ 代码。

这段代码背后的想法很简单，我们从左边开始计算一个数字出现的次数 x 直到我们到达一个不等于 x 的数字 y，因为我们的输入是排序的，它保证 x 永远不会出现在 y 之后。因此，检查 x 的出现次数是否为奇数就足够了。

请注意，如果数组未排序，则可以证明，你不能比 O(nlogn)

做得更好

 //Find odd numbers in given sorted list

#include <stdio.h>

int main(){
    
  int ArrayLength;
  scanf("%d",&ArrayLength);
  int array[ArrayLength];
  

  //Read input sorted array
  for ( int i = 0; i < ArrayLength; i++)
       scanf("%d",&array[i]);
       

  // Find numbers with odd occurrence 
  int PreviousLocalOdd=array[0];
  int LocalOdd=1;
  for ( int i = 1; i < ArrayLength; i++)
    {

        if (array[i]==PreviousLocalOdd)
            LocalOdd++;
        
        if(array[i]!= PreviousLocalOdd)    
          {  
                if(LocalOdd % 2==1)
                    printf("%d",array[i-1]);
            LocalOdd=1;
            PreviousLocalOdd=array[i];
          }
     
    }
       if(LocalOdd % 2==1)
        printf("%d ",array[ArrayLength-1]);


return 0;
}

查找列表中出现奇数次的元素

Find Elements occurring odd number of times in a list

python

algorithm

bit-manipulation

data-structures