算法总结——第K大相关问题总结

总结第K大相关问题

第K大数

题意非常简单，给出一堆乱序的数，让你找出这堆数中第k大的数

排序法

直接对这一堆乱序的数进行排序，然后取出第k大的数。这样做的时间复杂度是O(nlogn)

建堆法

首先对这些数建一个最大堆，然后再对最大堆堆顶的数pop k次，因为建堆的时间复杂度是O（4n）,所以整体的时间复杂度也是O(4n + klogn)

快排法

利用快排算法的思想进行变形，每次在数组中随机找一个拆分数，类似快排的思想把这个拆分数放到数组中应该存在的位置，判断拆分数排列第几，如果在k的后面表示第k个数需要在前半部分找；如果在k的前面表示需要后面半部分找。从而使规模一步一步缩小。

最后可以算出时间复杂度期望为O(n)，因为这取决于你拆分数的选取。

BFPRT算法

前面说了快排法能够使得其时间复杂度到达期望为O(n)，那能不能使得时间复杂度严格为O(n)呢？可以的，这里就引出了BFPRT算法。

首先我们可以来看一下BFPRT算法的步骤：

1. 分组（5个一组）
2. 小组内排序(对于每一组的排序的时间复杂度是O(1))
3. 把每个组的中位数拿出来组成一个新的数组
4. 使用BFPRT递归算出这个中位数组的中位数
5. 用这个当做划分值进行划分
6. 划分成两边以后递归调用直到找到第k个数

原理：
通过这样选到的划分数一定在0.3N-0.7N之间，如图所示

每次选取到的划分数一定都比红色的数要大，比蓝色的数要小

这样时间复杂度的迭代公式就是：

通过推导不难算出其时间复杂度严格为O(n)

前K大数

求前K大的数就无法做到时间复杂度为O(n)了，但是方法是相似的

最小堆法

1. 首先构造一个大小为k的最小堆
2. 从k+1个数开始，当比堆顶大，加入堆中并维持堆大小为k（维持可以通过限定索引做到）
3. 这样遍历了所有的数以后，堆中的这k个数就是前k个数了

快排法

依然可以用快排法

只不过在找到第k大的数之后需要对后面比这个数大的数进行一遍排序

参考：

• https://blog.csdn.net/jeffleo/article/details/64133292
• https://segmentfault.com/a/1190000009645951#articleHeader7