请问求第k大的数的方法以及各自的复杂度是怎样的，另外追问一下

[问答题]

请问求第k大的数的方法以及各自的复杂度是怎样的，另外追问一下，当有相同元素时，还可以使用什么不同的方法求第k大的元素

牛客363442233号

BFPRT算法能够做到时间复杂度就是 O(N) BFPRT算法，接收一个数组和一个K值，返回数组中的一个数

1. 数组被划分为了 N/5 个小部分，每个部分的5个数排序需要 O(1) ，所有部分排完需要 O(N/5)=O(N)

2. 取出每个小部分的中位数，一共有 N/5 个，递归调用BFPRT算法得到这些数中第 (N/5)/2 小的数（即这些数的中位数），记为 pivot

3. 以 pivot 作为比较，将整个数组划分为 <pivot , =pivot , >pivot 三个区域

4. 判断第K小的数在哪个区域，如果在 = 区域则直接返回 pivot ，如果在 < 或 > 区域，则将这个区域的数递归调用BFPRT算法

5. base case ：在某次递归调用BFPRT算法时发现这个区域只有一个数，那么这个数就是我们要找的数

2. 小顶堆

3. 快排

编辑于 2020-11-20 15:40:51 回复(0)

gapex

BFPRT算法，最差O(n)

发表于 2020-05-17 16:53:14 回复(0)

提交观点

问题信息

上传者：小小

难度：

2条回答 107收藏 969浏览

扫一扫，把题目装进口袋