如何在 40 亿个非负整数中找到所有未出现的数？

题目是这样的：

• 32 位无符号整数的范围是 ，即 ，现在有一个正好包含 40 亿个无符号整数的文件，所以在整个范围中必然有未出现过的数。可使用的内存有限，怎么找到所有未出现过的数？

大数据小内存问题，很容易想到位图法

我们申请一个长度为 的 bit 类型的位数组, 位数组上的每个位置只可以表示 0 或 1 状态。首先遍历这 40 亿个无符号数，例如，遇到 1000，就把 bitArr[1000] 设置为 1，这样，遍历第二遍的时候所有值为 0 的下标就是未出现的数。

简单算一下这种做法需要多大的内存空间：

8 个 bit 为 1B，所以长度为 42 9496 7295 的 bit 类型的数组占用 5 3687 0911 B 的空间，按照 1MB = 1024 * 1024 B 来算，那就是大概 500 多 MB 的空间大小

寻思一下，能不能有使用空间更小的做法？

=>

我们把 这个区间分为 份（当然你可以分得更多），这样，每个区间就是处理 个数，例如：第 0 区间 、第 1 区间 ，......

因为题目说一共只有 40 亿个数，而我们划分的区间是多于 40 亿的，所以，这样平均分的结果就是，肯定有几个区间是填不满 个数的。

更简单地解释下，比如我们按照 6 个数划分 3 个区间来算，每个区间就是存 2 个数对吧，但是假设现在实际上只有 5 个数，那么肯定有一个区间是存不满 2 个数的。

所以，如果一个区间填不满，也就意味着这个区间缺少了数，我们把这些区间拿出来，再依次按照位图法的那一套处理下，就能得到这些区间中未出现的数。

具体过程如下：

1）申请一个长度为 64 的整型数组 countArr[0..63], countArr[i] 用来统计区间 i 上的数有多少个，如果小于 ，说明这个区间上缺少了数

2）遍历 40 亿个数，根据当前数是多少来决定哪一个区间上的计数增加。例如，如果当前数是 3422552090，，所以下标未 51 区间上的计数增加，即 countArr[51]++

3）遍历完这 40 亿个数之后，遍历一遍 countArr，找出所有小于 的下标，假设是 {0，1}，那就表示第 0 区间 和第 1 区间 都存在未出现过的数

至此，我们只使用了一个 int[64]，大小为 64 * 4B = 256B，占用的内存非常小

4）接下来，我们需要对第 0 区间和第 1 区间进行进一步处理，也就是上面说过的位图法，以第 1 区间 为例：

• 申请长度为 的位数组，这仅仅占用大约 8 MB 的空间，记为 bitArr[0..67108863]
• 再遍历一次 40 亿个数，不过此时的遍历只需要关注落在第 1 区间上的数就行了，记为 num（），其他区间的数全部忽略
• 如果 num 在第 1 区间上，将 bitArr[num - 2^26 * 1] 的值设置为 1
• 这样，遍历完之后，在 bitArr 上必然存在没被设置成 1 的位置，假设第 i 个位置上的值仍然是 0，那么 2^26× 1 + i 这个数就是一个没出现过的数

总结来说，其实就是区间计数 + 位图法，对计数不足的区间执行位图法