Cracking the coding interview--Q5.7

January 4, 2013
作者:Hawstein
出处:http://hawstein.com/posts/5.7.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

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位,再计算出它的值即可。

代码如下:

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,即可找出丢失的那个整数。

代码如下:

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位,代码如下:

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;
}

完整代码如下:

#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