题目
给你一个文件，里面包含40亿个整数，写一个算法找出该文件中不包含的一个整数， 假设你有1GB内存可用。
如果你只有10MB的内存呢？
解答
我们先来做个算术题，40亿个整数大概有多大？
40 * 10^8 * 4B = 16GB (大约值，因为不是按照2的幂来做单位换算)
这个明显无法一次性装入内存中。但是，如果我们用计算机中的一位来表示某个数出现与否， 就可以减少内存使用量。比如在一块连续的内存区域，15出现，则将第15位置1。 这个就是Bit Map算法。关于这个算法，网上有篇文章写得挺通俗易懂的，推荐：
http://blog.csdn.net/hguisu/article/details/7880288
如果用Bit Map算法，一个整数用一位表示出现与否，需要的内存大小是：
40 * 10^8 b = 5 * 10^8 B = 0.5GB
而我们有1GB的内存，因此该算法可行。由于Bit Map只能处理非负数， (没有说在第-1位上置1的)，因此对于有符号整数，可以将所有的数加上0x7FFFFFFF， 将数据移动到正半轴，找到一个满足条件的数再减去0x7FFFFFFF即可。 因此本文只考虑无符号整数，对于有负数的情况，按照上面的方法处理即可。
我们遍历一遍文件，将出现的数对应的那一位置1，然后遍历这些位， 找到第一个有0的位即可，这一位对应的数没有出现。代码如下：
#include <iostream> #include <cstdio> using namespace std; int main(){ // freopen("12.3.in", "w", stdout); // int miss = 12345; // for(int i=0; i<20000; ++i){ // if(i == miss) continue; // cout<<i<<endl; // } // fclose(stdout); freopen("12.3.in", "r", stdin); int int_len = sizeof(int) * 8; int bit_len = 0xFFFFFFFF / int_len; int* bit = new int[bit_len]; int v; while(scanf("%d", &v) != EOF){ bit[v/int_len] |= 1<<(v%int_len); } bool found = false; for(int i=0; i<bit_len; ++i){ for(int j=0; j<int_len; ++j){ if((bit[i] & (1<<j)) == 0){ cout<<i*int_len + j<<endl; found = true; break; } } if(found) break; } delete[] bit; fclose(stdin); return 0; }
而我们有1GB的内存，因此该算法可行。由于Bit Map只能处理非负数， (没有说在第-1位上置1的)，因此对于有符号整数，可以将所有的数加上0x7FFFFFFF， 将数据移动到正半轴，找到一个满足条件的数再减去0x7FFFFFFF即可。 因此本文只考虑无符号整数，对于有负数的情况，按照上面的方法处理即可。
接下来我们就可以用Bit Map算法了。我们再遍历一遍数据， 把落在这个块的数对应的位置1(我们要先把这个数归约到0到blocksize之间)。 最后我们找到这个块中第一个为0的位，其对应的数就是一个没有出现在该文件中的数。 代码如下：
#include <iostream> #include <cstdio> using namespace std; int main(){ freopen("12.3.in", "r", stdin);// 20000 number int int_len = sizeof(int) * 8; int totalnum = 20000; int blocksize = 2000; int blocknum = totalnum / blocksize; int* block = new int[blocknum]; int* bit = new int[blocksize/int_len+1]; int v; while(scanf("%d", &v) != EOF){ ++block[v/blocksize]; } fclose(stdin); int start; for(int i=0; i<blocknum; ++i){ if(block[i] < blocksize){ start = i * blocksize; break; } } freopen("12.3.in", "r", stdin); while(scanf("%d", &v) != EOF){ if(v>=start && v<start+blocksize){ v -= start; // make v in [0, blocksize) bit[v/int_len] |= 1<<(v%int_len); } } bool found = false; for(int i=0; i<blocksize/int_len+1; ++i){ for(int j=0; j<int_len; ++j){ if((bit[i] & (1<<j)) == 0){ cout<<i*int_len+j+start<<endl; found = true; break; } } if(found) break; } delete[] block; delete[] bit; fclose(stdin); return 0; }
