Cracking the coding interview--Q12.4

Cracking the coding interview--Q12.4
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¹⁰ * 8位，大于32000，所以我们可以用Bit Map 来做这道题目。题目很简单，不过我们可以把代码写得漂亮一些。 我们可以写一个Bit Map类来完成基本的位操作。为了代码的简洁， 我们假设程序是运行在32位机器上，即int是32位的。如果考虑代码的通用性， 也可以将32替换成sizeof(int)*8。
http://blog.csdn.net/navyifanr/article/details/21334663

 public static void print_duplicates(int[] a,int n,int bitsize){
  BitMap bm=new BitMap(bitsize);
  for(int i=0;i<n;++i){
   if(bm.get(a[i]-1))  
    System.out.println(a[i]);
   else
    bm.set(a[i]-1);
  }
 }

class BitMap{
 public int[] bits;
 public BitMap(int size){
  bits=new int[size];
 }
 public boolean get(int pos){
  return (bits[pos/32]&(1<<(pos&0x1f)))!=0;
 }
 public void set(int pos){
  bits[pos/32]|=(1<<(pos&0x1f));
 }
}

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

Read full article from Cracking the coding interview--Q12.4