…
topK 一般解法
- 全局排序
- O（nlogn）的时间复杂度
- 数据量不大的时候简单可行
- 局部淘汰 / 局部排序
- 【类选择排序】对目标序列N个数遍历，取出其中最大的数最为Top1；再次遍历剩下的N-1个数，取出其中最大的数为Top2；….再对剩下的N-K+1个数遍历，取出其中最大的数为TopK。可以用冒泡k次实现
- O(n)的时间复杂度
- 【partition】每一轮排序都会将序列一分为二，左子区间的数都小于pivot，右子区间的数都大于pivot，按情况对左区间或右区间递归
- O(n)的时间复杂度
- 需要提前将N个数读入，空间开销较大；如果是动态数据，即可能会不停的增加新数据，那么就还需要每插入一个新数据就将其与前面取出的TopK做比较，排除K+1个数中最小的，最后剩下的才是TopK。
- 小根堆(优先队列)：只找到TopK，不排序TopK
- 先用前k个元素生成一个小顶堆，这个小顶堆用于存储当前最大的k个元素。
- 只需要将堆顶元素与下一个数比较：如果下一个数大于堆顶元素，则将当前的堆顶元素抛弃，并将该元素插入堆中。
- O(N * logk)的时间复杂度
- 对于海量数据，我们不需要一次性将全部数据取出来，可以一次只取一部分
- 对于动态数组，无论任何时候需要查询当前的前 K 大数据，我们都可以里立刻返回
小顶堆：每个结点的值都 <= 其左右孩子结点的值的【完全二叉树】
优先队列：在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先被访问（poll、delete…）。元素在队列尾追加。
堆 等效于 优先队列
海量数据
频率统计
找出一个数据流中最频繁出现的k个数，比如热门搜索词汇等。
例：统计一篇英文文章中频次出现最高的10个单词
- 数据量不大时可使用HashMap进行频率统计，求统计结果的topk
- Count-Min Sketch方法
- Trie树解决