怎么在线性时间内求 n 个数（可能有重复）内第 k 大的数

[ballshapesdsd]

在网上搜到了 BFPRT 算法的实现，发现如果 n 个数如果有重复就会变的很慢，自己研究了下算法没太看懂为什么。。有没有大神讲讲。。

[ballshapesdsd]

有人没

[crazybug]

不是大神瞎扯句。去重，排序。

[cabbage]

不是大神随便说说，hash 表

[Shura]

大根堆，不考虑建堆时间

[Shura]

@Shura 眼瞎，看成前 k 大数了

[ballshapesdsd]

@Shura 其实就是求前 k 大的数所在的位置。。之前用 python 的 heapq.nlargest，很慢，刚才发现 numpy 自带的 sort 和 c++的 BFPRT 算法效率差不多，甚至还更快。。所以就愉快的用 numpy 的 sort 了

[geelaw]

那你可以特判一下有很多相等的情况……原因和 naive 快排有相等元素可能变慢一样。

另一个方法是让两者强行不想等，比如额外记录原来的位置。但这样牺牲比较大。

[ballshapesdsd]

@geelaw 你的想法和这篇文章一样

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec01.pdf

[victor97]

基于快排的思路。
根据快排基准数的位置大于还是小于 k，决定是在前半部分还是后半部分继续找。
由于每次只看一边，所以时间复杂度是 O(n)。

[churchmice]

有种数据结构叫最大 /最小堆

[ballshapesdsd]

@victor97 这个算法的基准数不是随机选的，比较复杂

[zzj0311]

@ballshapesdsd 随不随机都是可以的～

[srlp]

日常 quickselect 够用了，平均 n，最差 n^2

[liuminghao233]

无论如何也要排序吧
On 是不可能 On 的除非已经排好的数
一般快排或堆排

[bumz]

分而治之

[lengyihan]

楼主是学生吧，在学算法，