🍕 大数据

32位无符号整数的范围是0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数? 【进阶】：内存限制为 3KB，甚至几个有限变量，但是只用找到一个没出现过的数即可。

【原问题 - 位图求解】： 无符号整数范围是 0~$2^{32}$，我们只保存这个范围，则只需要 $\frac{2^{32}}{8}$ = $2^{2}9$，即差不多 500M 的空间。 然后分批次遍历 40 亿个数字，将它们对应位置上的位 “涂黑”，最后结束时，没有被涂黑的位的下标，就是没有出现过的数字。

【进阶问题求解】:

• 首先，用 3KB 全部拿来创建无符号整型的数组，要求数组长度是 2 的幂次方，则这个数组长度最大将会是 $\frac{3000}{4}$ = 750 ≈ 512 = $2^9$。
• 有了 $2^9$ 长度的大小的数组后，计算 $\frac{2^{32}}{2^9}$ = $2^{23}$ = 8388608 。 这个数字就是词频统计的范围，即：
  • 数组的 0 位置统计 0~8388608 范围内有多少个数字；
  • 数组的 1 位置统计 8388609~16777217 范围内有多少个数字；
  • 数组的 2 位置统计 16777217~2*x-1 范围内有多少个数字。
• 然后，我们遍历 40 亿个数字，将每个数字除以 8388608，就能得到一个下标值，这个下标就是该数字所在的范围，将数字上的对应下标的值加 1
• 遍历一遍后，就可以得到每个范围内的词频。由于一定存在不重复的数字，所以选取词频统计最少得那个范围。
• 对那个范围继续进行 512 份划分，重复上面的步骤。继续遍历 40 亿个数字，只不过这一次我们只在乎最小词频范围内的数字，即只统计某一个范围内的词频。
• 统计结束后，一定又会有某个范围词频最小，继续对该范围 512 份划分。
• 最终肯定能够找到一个没出现过的数字。

更极端点，只用有限几个变量，每次都二分，每次二分后再次遍历 40 亿个数字，最多只需要遍历 32 次，就能找到没出现过的数字。