这是一个创建于 2932 天前的主题，其中的信息可能已经有所发展或是发生改变。
在网上搜到了 BFPRT 算法的实现，发现如果 n 个数如果有重复就会变的很慢，自己研究了下算法没太看懂为什么。。有没有大神讲讲。。
 |
1
ballshapesdsd OP 有人没
|
 |
2
crazybug 2017-10-21 17:16:06 +08:00 via Android
不是大神瞎扯句。去重，排序。
|
 |
3
cabbage 2017-10-21 17:19:52 +08:00 via Android
不是大神随便说说，hash 表
|
 |
4
Shura 2017-10-21 17:24:37 +08:00 via Android
大根堆，不考虑建堆时间
|
|
6
ballshapesdsd OP @Shura 其实就是求前 k 大的数所在的位置。。之前用 python 的 heapq.nlargest，很慢，刚才发现 numpy 自带的 sort 和 c++的 BFPRT 算法效率差不多，甚至还更快。。所以就愉快的用 numpy 的 sort 了
|
 |
7
geelaw 2017-10-21 17:38:47 +08:00 via iPhone
那你可以特判一下有很多相等的情况……原因和 naive 快排有相等元素可能变慢一样。
另一个方法是让两者强行不想等，比如额外记录原来的位置。但这样牺牲比较大。 |
|
8
ballshapesdsd OP |
 |
9
victor97 2017-10-21 19:01:14 +08:00 via Android  1
基于快排的思路。
根据快排基准数的位置大于还是小于 k，决定是在前半部分还是后半部分继续找。 由于每次只看一边，所以时间复杂度是 O(n)。 |
 |
10
churchmice 2017-10-21 19:10:18 +08:00 via Android
有种数据结构叫最大 /最小堆
|
|
11
ballshapesdsd OP @victor97 这个算法的基准数不是随机选的，比较复杂
|
 |
12
zzj0311 2017-10-21 19:20:00 +08:00 via Android
@ballshapesdsd 随不随机都是可以的～
|
 |
13
srlp 2017-10-21 19:41:34 +08:00 via iPhone
日常 quickselect 够用了，平均 n，最差 n^2
|
 |
14
liuminghao233 2017-10-21 19:48:47 +08:00 via iPhone
无论如何也要排序吧
On 是不可能 On 的除非已经排好的数 一般快排或堆排 |
 |
15
bumz 2017-10-21 19:52:15 +08:00
分而治之
|
 |
16
lengyihan 2017-10-22 01:02:28 +08:00 via Android
楼主是学生吧，在学算法，
|
Select Language