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

Question

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

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

我们不会返回新列表，也许会覆盖现有列表

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

我尝试过使用 XOR 进行按位操作，但无法解决问题。

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

直到我们到达不等于

y

的数字

x

，因为我们的输入已排序，所以保证

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;
}    

Answer 3

如果你想使用新列表，那么按照代码即可：

ls = [1,2,2,3,3,3,4,5,5,6,6,6,6,6] 
k=1
for i in range(len(ls)):
    item=ls[i]
    if (i+1 != len(ls)):
        item1=ls[i+1]
    else:
        item1=""
    if(item == item1):
        k=k+1
    else:
        if(k%2 != 0):
            print("Res=",item)
        k=1

但是如果您只想使用一个变量，请按照下一个代码操作：

ls = [1,2,2,3,3,3,4,5,5,6,6,6,6,6] 
l=len(ls)
i=0
while(True):
    item=ls[i]
    item1=ls[i+1]
    if(item == item1 ):
        ls.pop(i+1)
        ls.pop(i)
        i=i-1
    l=len(ls)
    i=i+1
    if(i+1 == l):
        break
print(ls)