这是一个创建于 1615 天前的主题，其中的信息可能已经有所发展或是发生改变。
原始数组只能从第一个开始访问一次，如何最快的在空间 O(m)的复杂度下找到第 m 个最大的数？
 |
1
msg7086 2020-06-07 17:26:07 +08:00  1
小顶堆？
|
 |
2
arjen 2020-06-07 17:27:39 +08:00 via Android 1
楼上正解，大小为 m 的小顶堆
|
 |
3
tesorouo OP |
|
4
arjen 2020-06-07 17:34:52 +08:00 via Android
@tesorouo 一次遍历就可以吧？每个元素与堆顶比较 ，比堆顶元素大即入堆，小则抛弃，最后堆顶元素为 top k 大元素。
|
 |
5
gzfrankie 2020-06-07 17:41:05 +08:00 via iPhone 2
小顶堆解法时间复杂度是 O(n+nlogm)，当 n 远大于 m 时，其实就是 O(n).据我所知没有更优解法。
|
 |
6
4rnold 2020-06-07 17:44:45 +08:00 1
[ [算法] Quick Select - LinMiaoj - 博客园]( https://www.cnblogs.com/LinMiaoJia/p/QuickSelect.html)
|
|
8
tesorouo OP @4rnold 我不知道我理解的对不对，但是这个如果是最初数组每个元素只能访问一次的情况下应该空间复杂度不止 O(m)
|
 |
9
gwy15 2020-06-07 18:08:06 +08:00 via Android 1
@tesorouo 这个可以原地 o1 空间，on 时间。就是快排只排一半。但是你要求单次遍历（只给一个单向迭代器），这个不适用
|
|
10
msg7086 2020-06-07 18:33:39 +08:00
|
 |
11
vindurriel 2020-06-07 19:33:57 +08:00 via iPhone 1
@tesorouo 楼主您题里说的是空间复杂度 O(m) 明显是堆 并没说时间复杂度 事实上实际场景里数组可以是无限长的 stream 在有限的内存里处理 此处空间复杂度比时间复杂度更有意义
|
|
12
tesorouo OP @vindurriel 对的我也是这样认为的，但是就是 O(n)的时间完全说不通，是一个比较偏向于理论的问题
|
 |
13
rrfeng 2020-06-07 19:43:00 +08:00 via Android 1
不用堆也可以啊，一个长 m 的数组，遍历到的数字往里做插入排序，遍历完最小的那个不就是么。
m 大的时候时间复杂度会比较高而已… 降低插入排序的办法可以用链表 当然堆可能是最好的 |
 |
14
rabbbit 2020-06-07 19:45:05 +08:00 1
双调排序可以做到 O(logn),但不符合只遍历一次.找出 k 个最大的数一般都是用堆排序.
|
|
15
tesorouo OP @rrfeng 这个应该是不对的，做插入的时候每次比较都是 O(m)，就算不看 m 的排序都有(n-m)个元素要进行这个操作，应该是差于堆的
|
 |
18
samlua 2020-06-07 20:07:17 +08:00 via iPhone
quick sort 的 partition ？每次放弃另一边 平均复杂度 O(n)
|
 |
21
opengps 2020-06-07 21:05:45 +08:00
woc，你们怎么又什么都懂
|
Select Language