在数组中查找奇数

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不在列表中

这是在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算法,在这种情况下非常有效(如果除了其中一个数字出现两次之外,列表实际上几乎已经完全排序了),那么它的复杂性大约是上).

Answer 2

你已经nums_copy.remove(i)这样了,你不能nums_copy.remove(i)再这样了

你可以这样做:

a = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]

def get_single_instance(array):
  d = {}

  for item in a:
    if item not in d:
      d[item] = 1
    else:
      d[item] += 1

  print d

  for k, v in d.iteritems():
    if v == 1:
      return k

print get_single_instance(a)

结果:9

Answer 3

最好的算法是使用 XOR 来查找奇数。

def find_number(nums):
    s = 0 
    for n in nums:
        s ^= n 
    return s 


a = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10] 
print(find_number(a))