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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2589 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

个数

算法

重复

bfprt

16 条回复 • 2017-10-22 01:02:28 +08:00

ballshapesdsd

2017-10-21 17:03:55 +08:00

有人没

crazybug

2017-10-21 17:16:06 +08:00 via Android

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

cabbage

2017-10-21 17:19:52 +08:00 via Android

不是大神随便说说，hash 表

Shura

2017-10-21 17:24:37 +08:00 via Android

大根堆，不考虑建堆时间

Shura

2017-10-21 17:25:35 +08:00 via Android

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

ballshapesdsd

2017-10-21 17:30:55 +08:00

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

geelaw

2017-10-21 17:38:47 +08:00 via iPhone

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

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

ballshapesdsd

2017-10-21 18:17:57 +08:00

@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

2017-10-21 19:01:14 +08:00 via Android

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

churchmice

2017-10-21 19:10:18 +08:00 via Android

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

ballshapesdsd

2017-10-21 19:11:12 +08:00

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

zzj0311

2017-10-21 19:20:00 +08:00 via Android

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

srlp

2017-10-21 19:41:34 +08:00 via iPhone

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

liuminghao233

2017-10-21 19:48:47 +08:00 via iPhone

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

bumz

2017-10-21 19:52:15 +08:00

分而治之

lengyihan

2017-10-22 01:02:28 +08:00 via Android

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