本文共 478 字，大约阅读时间需要 1 分钟。
问题A：
数组中最小k个数：维护k大小的大根堆，STL使用优先队列，时间O(NlogK)，空间O(k)
问题B：
数组中第k小的数：BFPRT算法，时间O(N)
int BFPRT(int Arr[],int K);
过程： 1，将Arr划分5个一组，组内排序找到下中位数，将每组下中位数放到新数组newArr中。 2，递归调用BFPRT(newArr, L/2)，找到newArr的中位数mid，mid划分Arr数组，小左大右，mid位置为 T 。 3，如果T == K，则程序结束；如果T < K，则递归调用BFPRT(Arr右，K-T)；否则，BFPRT(Arr左，K);总结：BFPRT通过找到稳定的伪中位数来淘汰较大一部分数据，达到O(N)
问题C：
数据流中位数：维护大小平衡的一个大根堆和一个小根堆 O(logN)
问题D：
数据流topK：哈希表+堆，时间O(N*logK)
哈希表，key为数字，times为出现次数，flag标记是否在堆中。
堆中只存放数字，但排序时使用哈希对应times来排序，使用flag来判断是否更新堆。
转载地址：http://dbwji.baihongyu.com/