如何快速查找数组中被替换为-1的原数字（元素为1~N）

除了常规线性遍历，最快的方法是利用数学求和或异或运算，两者都只需一次遍历数组，时间复杂度O(N)，空间复杂度O(1)，常数开销远低于逐个检查元素的线性搜索。

方法一：数学求和法 #

核心思路是用1到N的理论总和，减去数组实际总和的修正值，直接算出缺失数字：

• 先获取数组长度N，计算1到N的理论总和：S = N * (N + 1) // 2
• 遍历数组计算实际总和current_sum（直接把-1当作数值参与求和）
• 被替换的数字计算公式：x = S - (current_sum + 1)

推导逻辑 #

原数组总和是S，现在x被替换成-1，相当于实际总和 = S - x + (-1)，整理后就能得到x的计算公式。

示例 #

比如数组是[1, -1, 3]，N=3：

• 理论总和S = 3*4//2 = 6
• 实际总和current_sum = 1 + (-1) +3 =3
• x =6 - (3+1)=2，与缺失的数字一致。

方法二：异或运算 #

利用异或的两个关键特性：a ^ a = 0，0 ^ a = a，通过异或抵消重复值，定位目标数字：

• 先计算1到N所有数的异或结果xor_total
• 遍历数组计算所有元素的异或结果xor_current（直接包含-1的异或）
• 被替换的数字计算公式：x = xor_total ^ xor_current ^ (-1)

推导逻辑 #

原数组的异或结果是xor_total，替换后数组的异或结果 = xor_total ^ x ^ (-1)（把x换成-1，相当于异或x再异或-1），反向推导就能得到x的计算方式。

示例 #

还是用数组[1, -1, 3]，N=3：

• xor_total =1²3=0
• xor_current=1^-13=5（以3位二进制为例：001¹¹¹011=101）
• x=0⁵(-1)=2（101^111=010），结果正确。

适用场景 #

当N极大时，求和可能会出现整数溢出问题，而异或运算完全不会有这个顾虑，更适合超大数据量的场景。

内容的提问来源于stack exchange，提问作者Eternal_Explorer