40亿个非负整数中找到没出现的数

题目

• 原问题：32位无符号整数的范围是0-4294967295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。最多一可使用1GB的内存空间，怎么找到左右没出现过的数？
• 进阶：内存限制为10MB，但是只用找到一个没有出现过的数即可。

思路

1、原问题

如果用哈希表来保存出现过的数，那么如果40亿个数都不同，则哈希表记录为40亿条，每条记录占4B，共占用内存40亿*4B=160亿字节=16GB，内存不够用。可以用BitMap来表示出现过的数。具体做法是：

    1、申请一个长度为4294967295的bit类型的数组bitArr，bitArr上的没个位置有0，1两种状态，共占用内存500M。
    2、遍历这40亿个数，如遇到7000，就把bitArr[7000]置为1。
    3、遍历完成以后，再遍历bitArr，如果bitArr[i] = 00，则i没出现过，否则，i出现过，这样就可以吧所有的未出现的数均找出来。

2、进阶

    现在只有10M的内存空间，但只要求找到其中一个没出现过的数即可。首先，0-4294967295这个范围可以平均分成N个区间，每个区间是M个数，例如：第0区间(0， M-1)，第一区间(M, 2M-1)....第N-1区间(M*(n-1)-1，4294967295)。因为一共只有40亿个数，所以，如果统计落在每一个区间上的数有多少，肯定有一个区间的计数少于M。利用这一点可以找到其中一个没出现过的数。

具体做法是：
设N为64，则M为67108864。

• 1、第一次遍历时，先申请长度为64的数组countArr，用来统计每一个区间数出现的次数，遍历40亿个数，当前数为i， countArr[i/67108864]++。
• 2、第二次遍历，遍历countArr数组，找出countArr值小于67108864的区间，如countArr[51] < 67108864，则缺少的数在第51区间上。
• 3、第三次遍历，遍历40亿个数。
  3.1、申请长度为67108864的bitmap，占用大约8MB空间，即为bitmap[]。
  3.2、遍历40亿个数，此时只关注落在区间51上的数
  3.3、如果步骤2的num落在51区间，将bitmap[num]置1.
  3.4、遍历完40亿个数后，再遍历bitmap，如果其中的第i位没有置1，则67108864*51+i这个数就是没出过的数。

总结：

1、根据10MB的内存限制，确定统计区间的大小，就是bitArr的大小.
2、利用区间计数的方式，找到计数不足的区间，这个区间上肯定有没出现过的数。
3、对这个区间上的数做bitmap映射，再遍历bitmap，找到未出现的数。