原始数组只能从第一个开始访问一次，如何最快的在空间 O(m)的复杂度下找到第 m 个最大的数？
This topic created in 2341 days ago, the information mentioned may be changed or developed.
 |
1
小顶堆？
|
1 |
2
楼上正解，大小为 m 的小顶堆
|
 |
5
小顶堆解法时间复杂度是 O(n+nlogm)，当 n 远大于 m 时，其实就是 O(n).据我所知没有更优解法。
|
 |
6
[ [算法] Quick Select - LinMiaoj - 博客园]( https://www.cnblogs.com/LinMiaoJia/p/QuickSelect.html)
|
|
msg7086Jun 7, 2020
10
|
 |
11
@tesorouo 楼主您题里说的是空间复杂度 O(m) 明显是堆 并没说时间复杂度 事实上实际场景里数组可以是无限长的 stream 在有限的内存里处理 此处空间复杂度比时间复杂度更有意义
|
 |
12
@vindurriel 对的我也是这样认为的，但是就是 O(n)的时间完全说不通，是一个比较偏向于理论的问题
|
 |
13
不用堆也可以啊，一个长 m 的数组，遍历到的数字往里做插入排序，遍历完最小的那个不就是么。
m 大的时候时间复杂度会比较高而已… 降低插入排序的办法可以用链表 当然堆可能是最好的 |
 |
14
双调排序可以做到 O(logn),但不符合只遍历一次.找出 k 个最大的数一般都是用堆排序.
|
 |
samluaJun 7, 2020 via iPhone
18
quick sort 的 partition ？每次放弃另一边 平均复杂度 O(n)
|
 |
opengpsJun 7, 2020
21
woc，你们怎么又什么都懂
|
Select Language