algorithm - 给定 n-1*n 数组，找到缺失的数字

Question

这里每一行都包含一个数字的位表示。这些数字来自 1..N 恰好缺少一个数字。找到丢失数字的位表示。
面试官问了我这个问题。
我说：“我们可以找到给定数字的总和，然后从前 n 个数字的总和中减去它（我们称为 (N*(N+1))/2）”
他说这涉及从以 10 为底的更改为基数 2.
你能告诉我如何在不改变基数的情况下解决它吗？

Answer 1

您可以将..范围内的XOR所有数字放在一起，然后将数组中的数字放在一起。结果将是缺少的数字。0NXOR

解释： XOR将一个数字与自身结合总是导致零。上面的算法XOR对每个数字精确两次，除了缺少的一个。丢失的数字将被XOR-ed 与零恰好一次，因此结果将等于丢失的数字。

注意：面试官错误地认为需要转换基数才能进行加法：添加二进制数既简单又有趣 - 事实上，计算机一直都在这样做:-)

Answer 2

您可以将这些数字异或，然后与 1..n 异或。顺便说一句，数字以二进制形式存储的事实是一个很好的提示。

实际上，任何具有逆的交换运算符都应该起作用，因为如果运算符是可交换的，则顺序无关紧要，因此可以将其应用于您拥有的数字和 1..n，不同之处在于第一个不是对不在数组中的数字进行操作。然后你可以使用它的倒数来找到那个数字，你有两个结果。SO +and -, *and /, XORandXOR以及任何其他满足要求的运算符都应该在这里工作。