在网上搜到了 BFPRT 算法的实现，发现如果 n 个数如果有重复就会变的很慢，自己研究了下算法没太看懂为什么。。有没有大神讲讲。。
This topic created in 3310 days ago, the information mentioned may be changed or developed.
 |
1
有人没
|
 |
crazybugOct 21, 2017 via Android
2
不是大神瞎扯句。去重，排序。
|
 |
cabbageOct 21, 2017 via Android
3
不是大神随便说说，hash 表
|
 |
ShuraOct 21, 2017 via Android
4
大根堆，不考虑建堆时间
|
|
6
@Shura 其实就是求前 k 大的数所在的位置。。之前用 python 的 heapq.nlargest，很慢，刚才发现 numpy 自带的 sort 和 c++的 BFPRT 算法效率差不多，甚至还更快。。所以就愉快的用 numpy 的 sort 了
|
 |
geelawOct 21, 2017 via iPhone
7
那你可以特判一下有很多相等的情况……原因和 naive 快排有相等元素可能变慢一样。
另一个方法是让两者强行不想等，比如额外记录原来的位置。但这样牺牲比较大。 |
|
8
|
 |
9
基于快排的思路。
根据快排基准数的位置大于还是小于 k，决定是在前半部分还是后半部分继续找。 由于每次只看一边，所以时间复杂度是 O(n)。 |
1 |
churchmiceOct 21, 2017 via Android
10
有种数据结构叫最大 /最小堆
|
|
11
@victor97 这个算法的基准数不是随机选的，比较复杂
|
 |
zzj0311Oct 21, 2017 via Android
12
@ballshapesdsd 随不随机都是可以的～
|
 |
srlpOct 21, 2017 via iPhone
13
日常 quickselect 够用了，平均 n，最差 n^2
|
 |
liuminghao233Oct 21, 2017 via iPhone
14
无论如何也要排序吧
On 是不可能 On 的除非已经排好的数 一般快排或堆排 |
 |
bumzOct 21, 2017
15
分而治之
|
 |
lengyihanOct 22, 2017 via Android
16
楼主是学生吧，在学算法，
|
Select Language