这一类型题目通常要求在限定的系统资源内对大型数据进行操作，例如TopK、寻找重复值等。

解决思路

  1. 哈希函数分流进行分布式处理
  2. 布隆过滤器进行预过滤，从而减少真正要处理的数据量
  3. 利用并查集进行并行计算(**MapReduce**)
  4. 利用位图使得用较小的空间来代表大量的数据(某一个范围)

在位图中，可以用一个比特位表示一个数字从而缩小占用空间。例如int[2]的大小是64bit，就可以用来表示64个数字，比特位为1表示该数字存在，为0表示不存在。

  1. 堆、外排序思想
  2. 范围统计思想

    例题

    image.png
  • 方法一：

通过哈希算法将这100亿个URL分散到多个小文件中，重复的**URL**一定会被分散到一个文件当中，之后再对每个文件做重复检测即可。

  • 方法二：

通过布隆过滤器，过滤出一批可能重复的**URL** ,然后再做重复检测。
image.png
如果数据的规模较小，其实就是一个TopK问题，只需要构建一个长度恒为K的小顶堆，最终就能得到前100个数据。然后再进行排序即可。
这套题目是百亿级别的数据，使用哈希+ 堆来解决。首先将百亿数据根据哈希均匀地分散在多个文件中，分别构建词频表，并在每一个小文件中构建大根堆。
然后构建所有文件堆顶元素的大根堆，连续将堆顶元素出堆100次即可。
image.png

  • 方法一：

通过哈希分流，将数据均匀分流到多个文件中，然后依次在文件中执行计数操作，最后总和结果。

  • 方法二：

通过位图，用两个比特位来表示状态，即00表示没出现过，01表示1次，10表示两次，11表示更多次。40亿个无符号整数就是232左右，所以一共需要233个比特来表示所有的数字，也就是1G空间。
所以可以创建一个1G大小的整数数组，每个整数两个比特记录一个数字出现的次数，从而表示16个数字。
范围统计的运用
image.png
找到40亿个数的中位数，也就是找第20亿个数。可以将0-2**32**-1均匀分为多个区间，记录每个区间元素的个数，就可以找到第20亿个数所在的区间，然后在这个区间上再分区间寻找中位数，最终就能得到答案。
image.png
依次遍历40亿个数字，从而记录每个范围内数字出现的次数，就能够得到中位数所在的区间。然后再将这个区间均分为2**21**份继续执行。
如果只给了3个变量的空间，也可以这样做，直接将整个范围分为4份，然后不断统计即可。