从海量数据中找出不重复的数和出现次数最多的数的解决方案，分别采用了分治法+HashMap和位图法Bitmap两种方法。其中，位图法在大数据量下处理速度更快，内存占用更小。而对于其他类似问题，可以尝试使用分治法加最小堆/最大堆的方式处理。
原文链接：经典面试问题: Top K 之 ---- 海量数据找出现次数最多或，不重复的。
在数据处理中，较为棘手的有这么一种问题，海量数据如何进行处理。一旦数据的数量足够大，我们就不能使用常规的思路来解决。典型例子就是排序算法，在数据不大（不超过内存）的情况下，可以直接使用排序算法，但是当数据量很大时，我们就需要使用如多路归并此类的算法。
总结问题：
- 内存一次性不能放下所有的数
- 机器CPU核数不够
- ……
不重复数
在2.5亿个正整数中找出不重复的数。
分治法+HashMap
说明
比如将这些数据平均分为100个批次，每个批次就有250万数。每个批次用循环进行遍历，存入
HashMap<a, b>，a表示每个数，b表示对应数出现次数，默认为1。每遍历完一批，就对当前
HashMap进行去重，如果
b > 1，就排除此数。全部批次进行完筛选之后，剩下的数最后可以直接进行统计，得出不重复的数。
双间复杂度
时间复杂度：250W * 100轮 + 其他批次。 这里可以使用多核机器加速运算。
空间复杂度：int保存数，Key + Value（250W * 4Byte）/ (1024 * 1024)约为
(Key + 9.5M)内存
位图法 Bitmap
说明
设计每两个
bit位，标识一个数的出现情况。如：00表示没有出现，01表示出现一次，10表述出现多次。此题给出的是正整数，所以就是无符号的整型数，占四个字节。
内存的计算。1B=8b, 4B=32b, 它可以表示的最大整数是\(2^{32}-1\), 即需要$2^{32}-1 $约位\(2^{32}\)个位来表示这2.5亿个数，每个状态是两个数，总共就是\(2^{32}\times 2\)个位。
一次性申请的位图内存是: $2^{32} $ bit, 即\(\frac{2^{32}\times2}{(1024\times1024 \times 8)}=1\) GB。如果加上分治法，甚至都不需要1G内存。
假设一个数是64, 则对应的bit位是 \(64\times 2=128\)，即127和128共同标识这个数的出现状态（没有出现、出现一次、出现多次）。所以，每当读入了一个数，先找对应的bit位，如果是00就改为01，如果是01就改为10，如果是10就不需要修改。最后扫描整个位图，如果是10，就将下标/2得出出现次数为1的这个数。
出现次数最多的
- 找出一篇文章中，出现次数最多的单词
- 10亿个正整数找出重复次数最多的100个整数
这类问题被叫做Top K问题
分治法+HashMap
对于文章来说，我们需要规定每批次的字数限制。这里假设100为一批的处理极限，每次处理100个，如果最后一批少于100个就直接当作100来处理。之后每批文字进行切分(split)，比如英文的切割方法可以是空格、标点符号什么的，中文的切割方式可以是空格或者有预先准备好的词库。
之后就跟上面不重复数字的思路类似了，遍历每批数据，存入
HashMap<String, Integer>，String表示字符串，Integer对应出现的次数，最大的Integer就是出现次数最多的。
对数字来说，就是跟不重复数字思路类似，将十亿个数分乘很多份，利用
HashMap<int, int>来统计，最后找到第二个int最大的那个。每批筛选完之后，就进行排序，选出十亿个数中最大的。
位图法 Bitmap
对于文章（字符串）来说，不建议采用
对于数字来说，此题的背景不需要乘2，将每个数存进位图。出现了一次，bit位=1，没有出现就是0。但是没有办法统计出现次数，所以此题也不适合采用位图法。
其他
在XXX中找出最大、最小、最大的几个、最小的几个。都可以使用分治法+最小堆/最大堆。