python - 在由重复项组成的无序数组中查找唯一元素

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)。