[算法]海量数据问题之二

题目：

32位无符号整数的范围是0-2^32-1即0-4294967295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现的数。可以使用最多1GB的内存。

1.怎么知道所有没有出现过的数?

哈希表需要占用很多空间，可以使用bit map的方式来表示数出现的情况。具体地说，是申请一个长度为4294967295的bit类型的数组bitArr，bitArr上的每个位置只能表示0或1两个状态。8个bit为1B，所以长度为为4294967195的bit类型的数组占用500MB空间。

遍历这40亿个数，把遇到的数相应位置的值赋为1；

遍历整个数组，值为0的下标即为没有出现过的数。

2.内存限制为10MB，但是只要找到一个没出现过得数即可。

现在只有10MB的内存，但是也只要求找到其中一个没出现过的数即可。首先，0-2^32-1,这个范围是可以平均分成64个区间的，每个区间是67108864个数。如果统计落在每一个区间上的数有多少，肯定有至少一个区间上的计数少于67108864。具体过程为：

第一次遍历时，先申请长度为64的整形数组countArr[0..63],countArr[i]用来统计区间i上的数有多少。遍历40亿个数时，如果当前数为3422552090,3422552090/67108864=51,所以第51区间上的技术增加countArr[51]++。便利完40亿个数后，便利countArr，必然会出现某一位置上的值小于67108864，，表示该区间上至少有一个数没出现过。我们在该区间上继续寻找，此时使用的内存就是countArr的大小（64*4B），是非常小的。

假设找到第37区间上的计数小于67108864，以下为第二次遍历过程：

1.申请长度为67108864的bit map，这占用大约8MB的空间，记为bitArr[0..67108863];

2.再遍历一遍40亿个数，此时的遍历只关注落在第37区间上的数，记为num(num/67108864=37),其他区间的数全部忽略；

3.如果步骤2上的num落在第37区间上，将bitArr[num-67108864*37]的值设置为1，也就是做映射；

4.便利完40亿个数后，在bitArr上必然存在没被设置成1的位置，假设第i个位置上的值没设置成1，那么67108864*37+i，就是一个没出现过得数。

[算法]海量数据问题之二

原文：http://www.cnblogs.com/xiaomoxian/p/5161616.html