TopN解决方式？
答：
1. 10亿个数中如何高效地找到最大的一个数
将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的那个数据，最后在剩下的1000个数据里面找出最大的数据。 从100万个数据遍历选择最大的数，此方法需要每次的内存空间为10^6*4=4MB，一共需要1000次这样的比较。
2. 10亿个数中如何高效地找到第K个数
对于top K类问题，通常比较好的方案是分治+hash+小顶堆：
先将数据集按照Hash方法分解成多个小数据集
然后用小顶堆求出每个数据集中最大的K个数
最后在所有top K中求出最终的top K。
如果是top词频可以使用分治+ Trie树/hash +小顶堆：
先将数据集按照Hash方法分解成多个小数据集
然后使用Trie树或者Hash统计每个小数据集中的query词频
之后用小顶堆求出每个数据集中出频率最高的前K个数
最后在所有top K中求出最终的top K。
时间复杂度：建堆时间复杂度是O(K),算法的时间复杂度为O(NlogK)。
3. top K常用的方法
快排+选择排序：排序后的集合中进行查找
时间复杂度： 时间复杂度为O(NlogN)
缺点：需要比较大的内存，且效率低
局部淘汰：取前K个元素并排序，然后依次扫描剩余的元素，插入到排好序的序列中(二分查找)，并淘汰最小值。
时间复杂度： 时间复杂度为O(NlogK) (logK为二分查找的复杂度)。
分治法：将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的K个，最后在剩下的1000K个数据里面找出最大的K个，100万个数据里面查找最大的K个数据可以使用Partition的方法
时间复杂度： 时间复杂度为O(N+1000K)
Hash法： 如果这10亿个数里面有很多重复的数，先通过Hash法，把这10亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的K个数。
小顶堆： 首先读入前K个数来创建大小为K的小顶堆，建堆的时间复杂度为O(K)，然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。
时间复杂度： 时间复杂度为O(NlogK)
Trie树： 如果是从10亿个重复比较多的单词找高频词汇，数据集按照Hash方法分解成多个小数据集，然后使用Trie树统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
适用范围：数据量大，重复多，但是数据种类小可以放入内存
时间复杂度：O(Len*N)，N为字符串的个数,Len为字符串长度
桶排序：一个数据表分割成许多buckets，然后每个bucket各自排序，或用不同的排序算法，或者递归的使用bucket sort算法。也是典型的divide-and-conquer分而治之的策略。
使用范围：如果已知了数据的范围，那么可以划分合适大小的桶，直接借用桶排序的思路
时间复杂度：O(N*logM)，N 为待排序的元素的个数，M为桶的个数
计数排序：计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
适用范围：只能用在数据范围不大的场景
时间复杂度：O(N)
基数排序：将整数按位数切割成不同的数字，然后按每个位数分别比较。
适用范围：可以对字符串类型的关键字进行排序。
时间复杂度： O(N*M)，M为要排序的数据的位数
4. 实际情况
（1）单机+单核+足够大内存
- 顺序遍历（或先用HashMap求出每个词出现的频率）
- 查找10亿个查询次（每个占8B）中出现频率最高的10个，考虑到每个查询词占8B，则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存，直接在内存中对查询次进行排序，顺序遍历找出10个出现频率最大的即可。
- 优点： 简单快速
（2）单机+多核+足够大内存
- partition
- 直接在内存总使用Hash方法将数据划分成n个partition，每个partition交给一个线程处理，线程的处理逻辑同（1）类似，最后一个线程将结果归并。
- 瓶颈：数据倾斜。每个线程的处理速度可能不同，快的线程需要等待慢的线程。
- 解决的方法：将数据划分成c×n个partition（c>1），每个线程处理完当前partition后主动取下一个partition继续处理，知道所有数据处理完毕，最后由一个线程进行归并。
（3）单机+单核+受限内存
- 分治 + （1）
- 将原文件中的数据切割成M小文件，如果小文件仍大于内存大小，继续采用Hash的方法对数据文件进行分割，直到每个小文件小于内存大小，这样每个文件可放到内存中处理。采用（1）的方法依次处理每个小文件。
（4）多机+受限内存
- 数据分发 + （3）
- 将数据分发到多台机器上，每台机器采用（3）中的策略解决本地的数据。可采用hash+socket方法进行数据分发。
- MapReduce
- top K问题很适合采用MapReduce框架解决，用户只需编写一个Map函数和两个Reduce 函数，然后提交到Hadoop
- 首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上，最好可以让数据划分后一次读入内存，这样不同的机器负责处理不同的数值范围，实际上就是Map。
- 得到结果后，各个机器只需拿出各自出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是Reduce过程。
- 对于Map函数，采用Hash算法，将Hash值相同的数据交给同一个Reduce task；对于第一个Reduce函数，采用HashMap统计出每个词出现的频率，对于第二个Reduce 函数，统计所有Reduce task，输出数据中的top K即可。
