题目
有一个数组，里面的数在1到N之间，N最大为32000.数组中可能有重复的元素(即有的元素 存在2份)，你并不知道N是多少。给你4KB的内存，你怎么把数组中重复的元素打印出来。
解答
我们有4KB的内存，一共有4 * 210 * 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; }
