Cracking the coding interview--Q12.4

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

题目

原文:

You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array?

译文:

有一个数组,里面的数在1到N之间,N最大为32000.数组中可能有重复的元素(即有的元素 存在2份),你并不知道N是多少。给你4KB的内存,你怎么把数组中重复的元素打印出来。

解答

我们有4KB的内存,一共有4 * 2^10 * 8位,大于32000,所以我们可以用Bit Map 来做这道题目。题目很简单,不过我们可以把代码写得漂亮一些。 我们可以写一个Bit Map类来完成基本的位操作。为了代码的简洁, 我们假设程序是运行在32位机器上,即int是32位的。如果考虑代码的通用性, 也可以将32替换成sizeof(int)*8。 代码如下:

#include <iostream>
using namespace std;

class Bitmap{
public:
    Bitmap(int size = 32){
        bits = new int[size/32 + 1];
    }
    ~Bitmap(){
        delete[] bits;
    }
    bool get(int pos){// true if bit is 1, else: false
        return (bits[pos/32] & (1<<(pos&0x1f))) != 0;
    }
    void set(int pos){
        bits[pos/32] |= (1<<(pos&0x1f));
    }
private:
    int *bits;
};

void print_duplicates(int a[], int n, int bitsize){
    Bitmap bm(bitsize);
    for(int i=0; i<n; ++i){
        if(bm.get(a[i]-1)) // bitmap starts at 0, number starts at 1
            cout<<a[i]<<endl;
        else
            bm.set(a[i]-1);
    }
}
int main(){
    int a[] = {
        1,2,3,4,5,32000,7,8,9,10,11,1,2,13,15,16,32000,11,5,8
    };
    print_duplicates(a, 20, 32000);
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview