文章目录

• • 题目一
  • 题目二

海量数据小内存！如何找到高频数
海量数据小内存！从未出现过的数在哪里

题目一

如何在 40 亿个无符号整数中找到出现次数只有两次的那些数，在只提供 1 G 内存的条件下

解答

方法一【分流】：

单纯的将这些无符号整数放到 HashMap 中，大概率是会爆内存的，我们可以选择将这些无符号整数分流到很多个小文件中，然后使用 HashMap 对小文件中的数出现的频率进行统计，将只出现过两次的数保存到结果文件中

那么分流的方法就是，遍历这 40 亿个无符号整数，给他们都调用一个 Hash 函数，将结果模上小文件数，就可以实现将这些数均匀的分散的分流到小文件中

至于需要模上多少，即小文件的数量有多少，那就取决于提供的内存有多少，支持存多少条 Hash 记录。

比如，一条 Hash 记录至少 8 字节，就算会有其他的空间消费，我们就算一条记录 16 个字节，那么 1 G 可以申请 0.6 亿的数据，那么可以将 40 亿个数分成 70 个文件。其实，只要空间够用，分配较为合理，都是可以的

方法二【位图】：

根据之前的文章，我们可以知道，位图中的一个位是可以表示数有没有出现过的，比如出现过就标记为 1，始终没有出现过就一直都是 0。

那么现在想要表示出现两次的数，那么我们就可以使用两位来表示。00 表示该数从未出现过，01表示该数只出现过 1 次，10，表示该数出现过两次，11 表示该数出现超过两次。

40 亿个数，每个数使用两位，那么也就 80 亿位，即 10 亿字节，如果按照 1024 进行换算，消耗的内存是不会超过 1 G的

题目二

如何在 40 亿个无符号整数中找到中位数，在只提供 10 KB 的内存的条件下

解答

我们就把提供的 10 KB 内存统统用来申请无符号整形数组，看看最多能够不申请多少大小，并且数组的大小得是 2 的某次方，计算可得可申请大小为 2048 的无符号整形数组 array

那么我们就将无符号整数的范围（0~2³²-1）分成 2048 份，一定能够均分，每份包含的数据大小为 2 的 21 次方

然后，我们就需要遍历这 40 亿个数，计算各个值应该属于哪个范围，将数组 array 对应下标的值加一，比如 500 这个数，显而易见应该属于 0 ~ Y-1 这个范围，所以 array[0]++

遍历完全后，我们将每个范围的值进行累加，看看哪个范围刚好让累加值等于或者刚好超过 20 亿，那么中位数一定在那个范围中

如上图所示，可以发现累加到 array[2] 时，值刚好突破了 20 亿，那么就可以确定中位数就在 array[2] 所代表的的数值范围内。

接下来就是将目标范围内的数据（7亿）继续等分成 2048 份（每份范围大小为 2 的 10 次方），由于 array[0] 和 array[1] 的累加和为 15 亿，那么中位数就是 array[2] 中的第 5 亿个数（从小到大）

和上面的步骤一样，将中位数定在了 array[1] 区间范围内的数中，以此类推，最后总能找到目标数