题目
原文:
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。 代码如下:
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
#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
声明:自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证,转载请注明作者及出处
出处:http://hawstein.com/2013/01/30/12.4/