❓215. 数组中的第K个最大元素[中等]

题目信息

问题解答

暴力解法

https://leetcode-cn.com/submissions/detail/117217061/

function findKthLargest(nums: number[], k: number): number {
    return nums.sort((a, b) => b - a)[k - 1]
};

快速选择

最大元素小顶堆

建立一个容量为k的最大元素小顶堆

1. 创建一个堆 H[0……n-1]；
   
2. 把堆首（最大值）和堆尾互换；
   
3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
   
4. 重复步骤 2，直到堆的尺寸为 1。