《Cracking the Coding Interview》——第10章：可扩展性和存储空间限制——题目4
2014-04-24 21:26
题目：有一列数，范围全部在1~N之间，保证所有1~N之间的数字都会出现。如果你有4KB的内存，并且知道N最多是32000。请设计方法，找出N，并打印出所有有重复的数字。
解法：既然是“重复”，那就可以用位向量了。再考察N的范围，4KB内存有32768个位，足以容下至多32000个数字了。要找出N，就得找到第一个没有出现过的数字，扫描一次所有数字即可得到。对于重复的数字，也可以在一次扫描的过程中全部找出。对于扫描到的一个数字num，如果该数字还没出现过，则将标志位置为true；如果该数字的标志位已经为true，表示该数字存在重复，进行输出。
代码：
1 // 10.4 Assume you have a list of numbers. They range from 1 to N, where N is at most 32000. Some elements may have duplicates. You're given 4KB of memory, find out N and print the duplicates. 2 // 4KB means 32768bits, which is enough to hold 32000 numbers. Scan all the numbers and find out the duplicates. 3 // After the scanning is done, scan the bit vector to find the first '0' bit in the bit vector. It will be N. 4 int main() 5 { 6 return 0; 7 }