python - 找出数组中的奇数

Question

我正在尝试解决给我一个数组的问题，例如 [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]，其中所有数字都重复两次，排除一个数，我需要返回不重复的数。

我正在尝试这样做:

def findNumber(self, nums):

    if (len(nums) == 1):
        return nums[0]

    nums_copy = nums[:]

    for i in nums:
        nums_copy.remove(i)

        if i not in nums:
            return i
        else:
            nums_copy.remove(i)

但是当执行到else语句时，出现如下错误:

ValueError: list.remove(x): x not in list

这是i在nums_copy时出现的，所以我不明白为什么会在这种情况下出现这个错误？

Answer 1

比您最初的方法更简单(也更有效)的方法是使用 Counter对象:

 from collections import Counter

 singlet = Counter(nums).most_common()[-1][0]

Counter 对象将创建一个类似字典的对象，其键是列表中的值，值是它们出现的次数。 most_common 方法将返回按计数降序排列的 (value, count) 元组列表。

如果您不知道会有多少个单线态，您可以通过以下方式获得它们的列表:

[k for k, v in Counter(nums).items() if v == 1]

---

复杂性:

我说我的顶级解决方案更有效，因为您的原始实现遍历您的列表，并且对于每个项目都调用 remove 和 in 这将使您得到一些东西像 O(n²) 复杂度。在 Counter 实现中，Counter 对象的构造只对整个列表进行一次传递。 当 most_common 被调用时，可能会发生某种排序，所以我猜复杂度大约为 O(n log n)。 @Stefan Pochman 已就此纠正了我: Python 使用 Timsort这种算法在这种情况下非常有效(如果除其中一个数字以外的所有数字都出现两次，则该列表实际上已经几乎完全排序)因此其复杂度约为 O(n)。