如何在Python中高效遍历数字数组并查找缺失数值？

你的问题很典型——当数组规模变大时，线性查找的x not in array操作会带来O(n²)的时间复杂度，确实会拖慢效率。这里有几个更高效的解决方案，时间复杂度都是O(n)，远优于你当前的实现：

方法1：高斯求和法（最优空间效率） #

利用1到n的自然数求和公式，计算预期总和与数组实际总和的差值，这个差值就是缺失的数字。该方法只需要O(1)的额外空间，遍历一次数组即可完成计算。

array = [16, 11, 4, 6, 14, 8, 5, 13, 10, 2, 9, 15, 3, 18, 20, 12, 19, 7, 1]
n = len(array) + 1  # 因为数组缺失一个数，原序列应该有20个数字
expected_sum = n * (n + 1) // 2
actual_sum = sum(array)
missing_number = expected_sum - actual_sum
print(missing_number)  # 输出：17

原理：1到n的自然数和公式为n*(n+1)/2，用预期总和减去数组所有元素的和，剩下的就是没出现在数组里的数字。

方法2：集合查找法（平衡时间与空间） #

将数组转换为集合后，in操作的时间复杂度会从O(n)降到O(1)，从而把整体时间复杂度优化到O(n)。代价是需要O(n)的额外空间存储集合。

array = [16, 11, 4, 6, 14, 8, 5, 13, 10, 2, 9, 15, 3, 18, 20, 12, 19, 7, 1]
num_set = set(array)
n = len(array) + 1
for x in range(1, n+1):
    if x not in num_set:
        print(x)  # 输出：17
        break

原理：集合基于哈希表实现，查找操作的平均时间复杂度为O(1)，相比原方法的线性查找，效率提升非常明显。

方法3：异或法（避免大数溢出风险） #

利用异或运算的性质：a ^ a = 0，a ^ 0 = a。将1到n的所有数异或，再与数组中的所有数异或，最终结果就是缺失的数字。该方法同样是O(n)时间、O(1)空间，还能避免大数求和可能出现的溢出问题（虽然Python整数无溢出限制，但在其他语言中这个优势很明显）。

array = [16, 11, 4, 6, 14, 8, 5, 13, 10, 2, 9, 15, 3, 18, 20, 12, 19, 7, 1]
n = len(array) + 1
xor_result = 0

# 异或1到n的所有数字
for x in range(1, n+1):
    xor_result ^= x

# 异或数组中的所有数字
for num in array:
    xor_result ^= num

print(xor_result)  # 输出：17

原理：每个存在于数组中的数字会被异或两次（一次在1到n的遍历，一次在数组遍历），结果抵消为0；只有缺失的数字会被异或一次，最终保留在结果中。

复杂度对比 #

• 你的原方法：时间复杂度O(n²)，空间复杂度O(1)
• 上述三种高效方法：时间复杂度O(n)，空间复杂度分别为O(1)、O(n)、O(1)

对于数千甚至更大规模的数组，O(n)与O(n²)的效率差距会非常显著——比如n=1000时，原方法需要100万次操作，而高效方法只需要1000次左右。

内容的提问来源于stack exchange，提问作者E. Epstein