讨论/《堆》 - The Kth 问题/
共 6 个回复

The Kth 小元素 解法步骤:

  1. 建立一个k个元素的最大堆 ;
  2. 将其余元素如果小于最大堆的堆顶元素则删除堆顶元素,并把此元素插入到堆中;
  3. 取出堆顶元素即为第k小元素

The Kth 大元素 解法步骤:

  1. 建立一个k个元素的最小堆 ;
  2. 将其余元素如果大于最小堆的堆顶元素则删除堆顶元素,并把此元素插入到堆中;
  3. 取出堆顶元素即为第k大元素

时间复杂度 O(nlgk)
空间复杂度O(k)
这个步骤是不是会快一些?

3

的确没毛病,我尽快给加上。非常感谢!

谢谢建议!我后来也意识到这个问题了~

作者的画图非常有利于理解。
提一个改进点:
讲的有些繁琐,尤其是大顶堆和小顶堆操作都是一样的,实在没有必要都讲一遍。
另外,这个The Kth问题讲的和Top K问题一样,也没有必要,不如讲评论区提到的另一种方法。

是的 没必要完全堆化全部数组,只需要维持堆size为k

没错