找最大的第 m 个数问题

[tesorouo]

原始数组只能从第一个开始访问一次，如何最快的在空间 O(m)的复杂度下找到第 m 个最大的数？

[msg7086]

小顶堆？

[arjen]

楼上正解，大小为 m 的小顶堆

[tesorouo]

@arjen
@msg7086

小顶堆好像没办法做到时间 O(n) （即不为最快），答案说时间可以做到 O(n)，想破脑袋想不出。。

[arjen]

@tesorouo 一次遍历就可以吧？每个元素与堆顶比较 ，比堆顶元素大即入堆，小则抛弃，最后堆顶元素为 top k 大元素。

[gzfrankie]

小顶堆解法时间复杂度是 O(n+nlogm)，当 n 远大于 m 时，其实就是 O(n).据我所知没有更优解法。

[4rnold]

[ [算法] Quick Select - LinMiaoj - 博客园]( https://www.cnblogs.com/LinMiaoJia/p/QuickSelect.html)

[gwy15]

@4rnold 他要求一次遍历且不可修改。

[tesorouo]

@4rnold 我不知道我理解的对不对，但是这个如果是最初数组每个元素只能访问一次的情况下应该空间复杂度不止 O(m)

[gwy15]

@tesorouo 这个可以原地 o1 空间，on 时间。就是快排只排一半。但是你要求单次遍历（只给一个单向迭代器），这个不适用

[msg7086]

@tesorouo #3
每一次替换操作的时间复杂度是 logm，这里 m 相当于是题目给定的数字，算是常量，所以 logm 也是常量。
n+nlogm 的复杂度就等于是 O(n)了。

[vindurriel]

@tesorouo 楼主您题里说的是空间复杂度 O(m) 明显是堆 并没说时间复杂度 事实上实际场景里数组可以是无限长的 stream 在有限的内存里处理 此处空间复杂度比时间复杂度更有意义

[tesorouo]

@vindurriel 对的我也是这样认为的，但是就是 O(n)的时间完全说不通，是一个比较偏向于理论的问题

[rrfeng]

不用堆也可以啊，一个长 m 的数组，遍历到的数字往里做插入排序，遍历完最小的那个不就是么。
m 大的时候时间复杂度会比较高而已…

降低插入排序的办法可以用链表

当然堆可能是最好的

[rabbbit]

双调排序可以做到 O(logn),但不符合只遍历一次.找出 k 个最大的数一般都是用堆排序.

[tesorouo]

@rrfeng 这个应该是不对的，做插入的时候每次比较都是 O(m)，就算不看 m 的排序都有(n-m)个元素要进行这个操作，应该是差于堆的

[tesorouo]

@rabbbit 这个空间复杂度应该是超了很多了

[rabbbit]

@tesorouo
这个是并行排序算法,空间肯定是超的.

[samlua]

quick sort 的 partition ？每次放弃另一边 平均复杂度 O(n)

[samlua]

@samlua 失误 没有看清楚题目限制

[rrfeng]

@tesorouo
又没要求时间复杂度啊，而且我也说了会很高。如果不了解堆这是容易想到的一个思路。