代码战争的问题"Find the unique number"问题超时

Question

问题：

有一个数组包含一些数字。除一个数字外，所有数字都相等。试着找到它！

find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2
find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55

保证数组至少包含3个数字。

测试包含一些非常巨大的数组，所以请考虑性能。

我想知道如何提高性能。我发现使用set()可以提高性能，但我不明白为什么。

我的代码：

def find_uniq(arr):
for i in arr:
if arr.count(i)==1:
return i

我的代码会超时。

Answer 1

问题是代码的时间复杂性为O(n^2)。代码对列表中的所有数字进行迭代，并为每个数字调用arr.count()。方法arr.count()将不得不再次迭代完整列表，以计算项目出现的次数。因此，如果列表中包含n编号，则此代码必须执行n * n操作。这意味着，如果列表将变大1000倍，则需要1000000倍的时间才能解决。在这样的编码问题中，测试集通常至少包含一个列表，该列表太长，以至于在使用此类算法时会超时，但在使用更优化的算法时不会超时。

在这个特定的编程练习中，您知道每个列表只包含2个唯一的数字。一个数字正好出现1次，另一个数字出现(n-1)次。您可以使用set来查找O(n)时间中的2个唯一数字，然后仅在这2个项目上迭代，而不是在所有n项目上迭代：

def find_uniq(arr):
for number in set(arr):  # using set here!
if arr.count(number) == 1:
return number

该功能的正确性和性能可以用以下代码进行测试：

# Verify code with example input:
find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2
find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55
# Verify performance using a huge array (~1M elements):
huge_array = [1] * 1000000 + [2]
find_uniq(huge_array) == 2