在序列中找到缺失的数字

Question

我得到了一个包含n个整数的列表，这些整数的范围是1到n。列表中没有重复的数字。但是列表中缺失了一个整数。我需要找出这个缺失的整数。

Example: If n=8
I/P    [7,2,6,5,3,1,8]
O/P    4

I am using a simple concept to find the missing number which is to get the 
sum of numbers 
       total = n*(n+1)/2
And then Subtract all the numbers from sum.

然而，如果数字总和超过允许的最大整数，则上述方法将失败。

因此，我搜索了第二种解决方案，并找到了以下方法：

 1) XOR all the elements present in arr[], let the result of XOR be R1.
 2) XOR all numbers from 1 to n, let XOR be R2.
 3) XOR of R1 and R2 gives the missing number.

这种方法是如何工作的？..在上述情况下，R1和R2的异或如何找到缺失的整数？

- poorvank

---

那我们来试试暴力破解吧？先对数组进行排序，然后检查哪些索引对应的 [n - (n-1)] 不等于 1。 - Geeky Guy

为什么会有一个允许的最大整数限制呢？ - VoronoiPotato

@VoronoiPotato：如果序列中有10亿个数字，并且他只能使用32位整数，那该怎么办？ - Jim Mischel

@Renan因为那样会更慢吗？而且，无论如何，OP并不是在寻求替代方案，而是想知道为什么/如何提出的解决方案有效。 - harold

Answer 1

回答你的问题，你只需要记住

A XOR B = C => C XOR A = B

因此，它立即跟随

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL) => 
(TOTAL) XOR ( PATIAL SUM) = (MISSING ELEMNT)

为了证明第一个性质，只需要写出异或（XOR）的真值表：

A B | A XOR B
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

简述真值表：如果两个位相同，XOR的结果为假，否则为真。

另外需要说明的是，XOR的这种性质使它成为简单（但不是微不足道的）加密形式的良好选择。

- Save

Answer 2

首先，在出现整数溢出的情况下，您可以使原始方法正常工作（只要 n 在int范围内）。

至于异或方法，注意到 R1 xor M == R2（其中M是缺失的数字）。由此可知 R1 xor M xor R2 == 0，因此M == R1 xor R2。

- NPE

Answer 3

XOR的原理是，每当你将一个位与1进行XOR运算时，它就会翻转，而每当你将一个位与0进行XOR运算时，它就保持不变。因此，对除了缺失数字以外的所有数据进行XOR运算的结果给出了XOR所有数字的'负面'印象。这两个结果进行XOR运算后可以恢复你丢失的数字。

- Paul Evans

Answer 4

让我们只看低位比特（LOB）的异或，以保持简单。假设x是缺失的整数。

列表中的每个整数都为R1的LOB（LOB（R1））提供1或0。

在范围内的每个整数都会向LOB（R2）提供1或0。

现在假设LOB（R1）== LOB（R2）。由于R2 == R2 XOR x，这只能发生如果LOB（x）== 0 == LOB（R1）XOR LOB（R2）。 （1 xor 1 = 0，0 xor 0 = 0）

或者假设（LOB（R1）== LOB（R2）。只有当LOB（x）== 1 == LOB（R1）XOR LOB（R2）（1 xor 0 = 1，0 xor 1 = 1）时，才会发生这种情况。

但对于所有位而言，低位比特起作用，因为按位独立计算XOR。

- Codie CodeMonkey