每周算法之TopK问题
1. 问题描述
海量数据处理中经常会遇到统计出现频次最高的K个关键词或者从数字中统计出最大的前K个数，这就是经典的TopK问题。
2. 解决思路
- 方案一：通过快速排序进行全排序，找到最大的前k个数。复杂度为O(n*lgn)
- 方案二：避免全排序，只对最大的K个排序。比如通过冒泡排序的方式，冒k次泡，找出k个最大值。复杂度为O(n*k)
- 方案三：找出k个最大值，不排序。通过建立小根堆，建立大小为k的小根堆，然后遍历剩下的n-k个数。每次跟堆顶的数比较，大于堆顶的值则覆盖，重新调整堆为小顶堆，直到遍历完n-k个数为止。复杂度为O(n*lgk)
- 方案四：针对方案一快速排序的改进。快排属于分治算法，这里通过减治的方式，将只针对包含最大k个值的这一侧进行快排处理。
备注：
分治法：大问题分解为小问题，小问题都要递归各个分支，例如：快速排序
减治法：大问题分解为小问题，小问题只要递归一个分支，例如：二分查找，随机选择
考虑到数据集很大，内存无法全部容纳。