algorithm - 在位数组中查找缺失的数字

Question

这个问题直接取自Cracking the Coding Interview, 4th Ed ，所以我不是 100% 确定我可以在这里发布它；如果没有，请告诉我，我会删除它。

问题 5.7:

An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single opera-tion. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

我知道如何解决这个问题。我不明白的是，她 是如何解决的。她的方法:

1. 从最小符号位开始。
2. 计算 1 与 0 的出现次数。
3. 如果 count(1) < count(0) => 缺失的数字是 1，因为它是最小符号位，否则它是 0。
4. 删除所有最小符号位与步骤 3 中找到的结果不匹配的数字。
5. 重复步骤 1->4，从最小信号位开始迭代 -> 第二个最小信号位 -> ... -> 最大信号位

当 n 的形式为 (2^m)-1 时，我可以看到这个工作对于一些积极的 m...但是看不出它在一般情况下是如何工作的。

考虑二进制基数中的自然数。然后第 i 个最小 sig 位的序列如下:

1. 0,1,0,1,0,1,0,... = {01}* = {(1)0(1)1}*
2. 0,0,1,1,0,0,1,1,... = {0011}* = {(2)0(2)1}*
3. 0,0,0,1,1,1,0,0,0,... = {000111}* = {(3)0(3)1}*

那么对于一些 s，最高 sig 位有一些序列 {(s)0(s)1}。如果n=(2^m)-1，那么一切都很好；对于每个量级，#1s = #0's，因此我们可以使用作者的逻辑。 但是，这在一般情况下是如何工作的？如果 n 是某个任意数，则导致 n 的 most-sig 位序列如下所示:(s)0(s)1(s)0(s) 1...(k)1(很明显，序列必须以 1 作为最大 sig 位结束)，k 可以是 [0,s] 中的任何数字。那么她的逻辑如何适用呢？ (最值得注意的是，第 3 步假设在通常情况下，#0 最多比 #1 多 1)

谢谢，如果有人能对此有所了解!谢谢!

Answer 1

有3种可能:

1. n 是奇数，所以0 位数和1 位数应该相同。他们不会，所以较低的数字显然是缺失的那个。
2. n 是偶数，所以0 的位数应该比1 的位数多1。如果它们相等，则缺少 0 位。
3. 如上，n 是偶数。如果 0 位数比 1 位数大 2，则 1 位是缺失的一位。

通过删除所有已消除的数字，您现在递归地再次应用完全相同的问题。