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