在位数组中找到缺少的数字

Question

这个问题直接来自Cracking the Coding Interview,4th Ed,所以我不是百分百肯定我可以在这里发布; 如果没有,请告诉我,我会删除它.

问题5.7:

数组A [1..n]包含从0到n的所有整数,但缺少一个数字.在这个问题中,我们无法通过单个操作访问A中的整个整数.A的元素被表示为二进制的,我们可以用它来访问他们的唯一操作是"取A [1]的第j个比特",这需要一定的时间.编写代码以查找缺少的整数.你能在O(n)时间做吗？

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

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

我可以看到这种方法在n为某些正m的形式(2 ^ m)-1时有效...但是在一般情况下看不出它是如何工作的.

考虑二进制基数中的自然数.然后第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,因此我们可以使用作者逻辑.但是,这在一般情况下如何运作？如果n是某个任意数,则导致n的大多数sig位的序列如下所示:(s)0(s)1(s)0(s)1 ...(k)1(显然序列必须结束1为最大sig位),k可以是[0,s]中的任意数字.那么她的逻辑如何应用？(最值得注意的是,第3步假设#0在通常情况下最多比#1更多1)

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

Answer 1

有三种可能性:

1. n是奇数,所以0位数和1位数应该相同.它们不会,所以较低的数字显然是缺失的数字.
2. n是偶数,所以0位数应该比1位数大1.如果他们是平等的,0那就是缺少的.
3. 如上所述,n甚至是.如果0位数比位数大2 1,则该1位是丢失的位.

通过删除已消除的所有数字,您现在再次以递归方式应用完全相同的问题.