题目
原文：
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 operation. 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?
译文：
数组A[1…n]包含0到n的所有整数，但有一个整数丢失了。在这个问题中， 我们不能直接通过A[i]取得数组中的第i个数。数组A被表示成二进制， 也就是一串的0/1字符，而我们唯一能使用的操作只有“取得A[i]中的第j位”， 这个操作只需要花费常数时间。写程序找出丢失的整数，你能使程序的时间复杂度是O(n)吗？
解答
首先，在这个问题中，明确我们唯一能使用的操作是fetch(a, i, j)即： 取得a[i]中的第j位。它是提供给我们的操作，怎么实现的不用去理它， 而我们要利用它来解决这个问题，并且在我们的程序中，不能使用a[i]这样的操作。
如果我们不能直接使用a[i]，那么我们能利用fetch函数来获得a[i]吗？回答是可以。 数组a中每个元素是一个整型数，所以只要每次取出32位，再计算出它的值即可。
代码如下：
1
2
3
4
5
6
int get(int a[], int i){
int ret = 0;
for(int j=31; j>=0; --j)
ret = (ret << 1) | fetch(a, i, j);
return ret;
}
我们已经通过get(a, i)来取得a[i]的值了，这样一来，我们只需要开一个bool数组， 把出现过的整数标记为true，即可找出丢失的那个整数。
代码如下：
1
2
3
4
5
6
7
8
9
10
int missing(int a[], int n){
bool *b = new bool[n+1];
memset(b, false, (n+1)*sizeof(bool));
for(int i=0; i<n; ++i)
b[get(a, i)] = true;
for(int i=0; i<n+1; ++i){
if(!b[i]) return i;
}
delete[] b;
}
我们把问题再变难一点点，如果我们能取到的只是数组a中的第j位，即有函数fetch(a, j)，
而不是取到a[i]中的第j位，那又应该怎么做呢。其实也很简单，
计算a[i]需要取出a[i]中的第31位到第0位(共32位)，对应到整个数组上，
就是数组从头开始数起，取出第32*i+31位到第32*i位，代码如下：
1
2
3
4
5
6
7
int get1(int a[], int i){
int ret = 0;
int base = 32*i;
for(int j=base+31; j>=base; --j)
ret = (ret << 1) | fetch1(a, j);
return ret;
}
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstring>
using namespace std;
int fetch(int a[], int i, int j){
return (a[i] >> j) & 1; //return 0/1
}
int get(int a[], int i){
int ret = 0;
for(int j=31; j>=0; --j)
ret = (ret << 1) | fetch(a, i, j);
return ret;
}
int missing(int a[], int n){
bool *b = new bool[n+1];
memset(b, false, (n+1)*sizeof(bool));
for(int i=0; i<n; ++i)
b[get(a, i)] = true;
for(int i=0; i<n+1; ++i){
if(!b[i]) return i;
}
delete[] b;
}
int fetch1(int a[], int j){
return (a[j/32] >> (j % 32)) & 1;
}
int get1(int a[], int i){
int ret = 0;
int base = 32*i;
for(int j=base+31; j>=base; --j)
ret = (ret << 1) | fetch1(a, j);
return ret;
}
int missing1(int a[], int n){
bool *b = new bool[n+1];
memset(b, false, (n+1)*sizeof(bool));
for(int i=0; i<n; ++i)
b[get1(a, i)] = true;
for(int i=0; i<n+1; ++i){
if(!b[i]) return i;
}
delete[] b;
}
int main(){
int a[] = {
0, 1, 2, 3, 4, 5, 7, 8, 9, 10
};
cout<<missing(a, 10)<<endl;
cout<<missing1(a, 10)<<endl;
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/01/04/5.7/
