本文主要是介绍TopK问题解决方案，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题：给定一个海量数据的n，要求从n中提取出最大/最小/重复频度最高的K个数（K相对于n较小，如n为10亿量级，而K为100）
解决方案：
方案1：n个数排序，选取排序后的第k个数，时间复杂度为O(nlogn)。使用STL函数sort可以大大减少编码量。
方案2：维护K个元素的最大堆，每次和堆顶元素比较，然后堆化，时间复杂度为O(nlogK)，时间复杂度比方案1好，毕竟K一般是远远小于n的。
方案3：BFPRT算法（中位数的中位数算法），快排的变形，最坏情况下时间复杂度为O(n)。
一趟快速排序的过程如下
（1）先从序列中选取一个数作为基准数
（2）将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边
一趟快速排序也叫做Partion，即将序列划分为两部分，一部分比基准数小，另一部分比基准数大，然后再进行分治过程。
因为每一次Partion不一定都能保证划分得很均匀，所以最坏情况下的时间复杂度还是O(n2)
在BFPTR算法中，仅仅是改变了快速排序Partion中的pivot值的选取，在快速排序中，我们始终选择第一个元素或者最后一个元素作为pivot。而在BFPTR算法中，每次选择五分中位数的中位数作为pivot，这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。
将序列按5个元素一组划分为多组
将每组按降序排序，选出每组的中位数
对上面选出的中位数递归进行步骤1和步骤2，直到只剩下一个数即为中心数
基于中心数为pivot对序列进行快排
这篇关于TopK问题解决方案的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
