未出现的数

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

思路：准备一个长度为 2 的 bit 类型的数组，即长度为 2 的 byte 数组。大概为 500+ M。每个位置上用 0 表示不存在数，1 表示存在数。

代码实现：此处直接使用数组代替了读文件

static List<Integer> findNotExist(int[] arr) {
    // 一个 int = 32 个 bit
    int[] flagArr = new int[(int) Math.pow(2, 32) / 32];
    for (int i : arr) {
        int numIndex = i / 32;
        int bitIndex = i % 32;
        flagArr[numIndex] = flagArr[numIndex] | (1 << bitIndex);
    }
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < flagArr.length; i++) {
        int num = flagArr[i];
        for (int j = 0; j < 32; j++) {
            // 每个位置是是否为 0
            if ((num & (1 << j)) == 0) {
                list.add(i * 32 + j);
            }
        }
    }
    return list;
}

【进阶】
内存限制为 10MB，但是只用找到一个没出现过的数即可

进阶思路**：限制内存为 10 M。其实我们可以将限制变得更小点，比如限制为 3 KB，步骤为

因为一个 int 为四个 byte，3000/4 ≈ 700+，最接近 700 的 2 的幂为 2 = 512，那么我们可以新建一个长度为 512 的 int 数组 int[] frequency = new int[512]。
遍历大文件，当前遍历到的数据为 num，则 frequency[num/512]++;。frequency数组中记录的是将文件分为 512 份儿后每个范围有 2^32 / 512 个数，遍历大文件后出现在该范围数字的频率。
遍历后一定有 frequency[i] < (2^32 / 512)，那么在该范围（[2^32 / 512 * i, 2^32 / 512 * (i+1)]）中一定有未出现的数。然后将该范围分为 512 份儿，重复步骤2，知道能确定某个具体的数为出现过

在极端情况下，只使用 3 个变量也可以做到：
将大文件遍历，每次都只分为两部分，在出现的频率小于 232/2 的范围上继续二分，一直二分下去，直到找到某个具体未出现过的数

重复的 URL

有一个包含100亿个 URL 的大文件，假设每个 URL 占用64B，请找出其中所有重复的 URL

思路：把大文件使用哈希函数分割成一个个的小文件，这样重复的都会被分到以前，然后依次遍历每个小文件就能得到所有重复的 URL

【补充】
某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种求出每天热门 Top100 词汇的可行办法，实际场景：微博热门话题

这个补充题目的思路和找到重复 URL 的思路基本一致，但是只需要找到 Top 100 就可以所以这样做：

使用哈希函数将所有词汇分割到 n 个小容器中
对每个容器分别进行词频统计，生成一个容量为 100 的大根堆
弹出每个容器大根堆的堆顶，将他们组成一个容量为 n 的大根堆 TopHeap
从 TopHeap 中弹出 100 个词，每弹出一个词，就从弹出词的源容器中再弹出堆顶加入 TopHeap。例如 TopHeap 中弹出的是“Java”，“Java”来自二号小容器的大根堆，那么就从二号小容器弹出堆顶加入到 TopHeap 中。
弹出的 100 个词就是 Top100

这相当于是一个二维堆的结构，由于堆的调整都是的，效率也很高

输出有序文件

存在一个 10G 的文件保存着一些无序 int 类型的数字，要求：最多使用 5G 内存来将这个文件中的所有数输出到一个新的文件，并且有序。

思路：
先将数据按照大小分段到不同小文件中，保证每个小文件都小于最小内存。分别排序每个小文件后按顺序输出到大文件中。

以上方法一定能解决问题，但是还可以做很多优化，具体步骤为：

建立一个数据结构
```
class Num {
  int value; // 数
  int time; // 该数出现的次数
}
```
计算上面的结构需要多少空间，两个 int 使用 8b，但是数据本身会放到各种结构中，所以要多算一些空间，这里预估为 16b。
5G 内存可以保存 5G/16b 大概有 3000+ 万条记录，最接近这个数的 2 的幂为 2。
int 的范围为 [-2, 2-1]，将大文件遍历，分为 2/2= 2 个文件，每个文件范围为 2个数
按顺序遍历每个小文件中的值统计成 Num 结构，按照 value 组成一个小根堆
将小根堆弹出输入到新的文件中
遍历下个小文件，直到遍历所有的小文件

中位数

32 位无符号整数的范围是0~4294967295，现在有 40亿个无符号整数，可以使用最多 1GB 的内存，找出所有出现了两次的数。

思路：
这个题目看着似曾相识，和找 未出现的数 类似，但是如果使用相同的思路解决会出现问题：在原题中只需要用 0、1 记录某数是否出现过，这里还需要记录出现的次数

可以这样来解决：

方法一：将大文件通过哈希函数分割成多个小文件，对每个小文件进行统计，然后就可以找到
方法二：对原先的位图进行修改，用两个bit来表示：
- 00：该数未出现
- 01：出现了一次
- 10：出现了两次
- 11：出现了两次以上

这个思路还可以解决出现 n 次的数，只需相应的足够多的 bit 位来表示次数就 OK

【补充】
可以使用最多 10MB 的内存，怎么找到这40亿个整数的中位数？

思路：
这个题目和 未出现的数 的进阶：内存限制为 10MB，但是只用找到一个没出现过的数即可类似。可以采用同一思路来解决，为了方便举例，将内存限制缩小到 10 K：

将文件分为 10Kb/4b = 2500，和 2500 最接近的 2 的幂为 2 = 2048，可以将文件分为 2048 份儿
遍历大文件，统计每个小文件对应范围内出现的数的次数
遍历完成后，将每个小文件出现的次数相加，当相加的结果超过了 20亿，说明中位数就在该小文件中
然后在将该文件等分 2048 份儿，再统计……循环下去，直到统计到具体的某个数就是中位数

或者可以将思路进行修改：

将大文件分成 n 个小于 10M 的小文件，然后遍历统计词频
统计完成后将统计结果相加，找到中位数在某个小文件的范围中
由于该小文件本身小于 10M，这可以直接放到内存中遍历找到中位数
总结

这七个技巧基本囊括了所有资源限制类题目的解法：

哈希函数的离散性和均匀性：可以找到大量数据中出现最多的数
布隆过滤器：黑名单设计、爬虫的 URL 重复
一致性哈希：负载问题、扩容问题
并查集：解决岛问题、MapReduce
位图：解决未出现的数，出现重复 n 次的数
分段统计：在大量数据中找到符合要求的数：如中位数
堆：处理大量数据时，一般配合分段统计使用，解决热门词汇，Top N 等按照某标准排序的问题

算法

资源限制题

未出现的数

重复的 URL

输出有序文件

中位数

总结