在包含重复项的无序数组中查找唯一元素

Question

例如,如果L = [1,4,2,6,4,3,2,6,3],那么我们希望1作为唯一元素.这是我想到的伪代码:

初始化字典以存储每个元素的出现次数:~O(n),查看字典以找到值为1的元素:~O(n)

这确保了总时间复杂度保持为O(n).这看起来是正确的想法吗？

此外,如果对数组进行了排序,例如,时间复杂度会如何变化？我认为这将是二进制搜索的一些变体,它会将其减少到O(log n).

Answer 1

您可以使用 collections.Counter

from collections import Counter

uniques = [k for k, cnt in Counter(L).items() if cnt == 1]

复杂性永远是O(n).您只需要遍历列表一次(这就是Counter正在做的事情).排序无关紧要,因为字典赋值始终为O(1).

Answer 2

有一个非常简单的解决方案是使用^运算符将序列的O(n):XOR元素组合在一起.变量的结束值将是唯一编号的值.

证明很简单:对一个数字进行异或运算产生零,所以由于除了一个数字之外的每个数字都包含它自己的副本,因此对它们进行异或运算的最终结果将为零.将唯一数字与零进行异或运算得出数字本身.