最近我接到了以下任务：
假设您有一个长度为N的元素数组，其中除了两个special之外的每个元素都出现一次，恰好出现两次。找到这个特殊号码。
我也知道数组中的每个元素都是非负的，并且不超过 10^9 并且数组的长度，N小于或等于 10^6
我认为解决方案是使用 xors。这是我的想法：
让我们对数组中的所有元素进行异或。由于 xor 是可交换的，例如 xor(a, b)=xor(b, a)，我们可以得出结论，所有出现两次的元素都将归零：
xor(a, b, a, c)=xor(a, a, b, c)=xor(xor(a, a), b, c)=xor(0, b, c)=xor(b, c) )
然后对整个数组进行异或运算，我们将得到两个特殊元素的异或。接下来做什么？也许，其他一些解决方案？
PS请不要告诉我有关哈希表的任何信息。首先，我已经尝试过了，但是没有用，因为我的哈希函数无法将所有范围的数字压缩到任何合理大小的数组中（至少对于我的机器而言）。其次，它被任务的条件所禁止。
编辑：我的错，我没有提到排序也被禁止。
MBo*_*MBo 10
Xoring 很好的方法。
试想 - 异或所有元素的结果是什么？正如您所写，所有配对元素都归零，因此结果是
R = A xor B
考虑一个比特的结果R-我们可以看到，它们对应于不同的比特A和B。
所以我们可以选择 的任何非零位R，并进行第二次运行 - 但只对具有该位非零的元素进行异或。
现在我们有了新的结果 - 它是 equal 或Aany B。
计算第二个是基本的： B = R xor A
复杂性保持线性 O(n)