一、问题描述
在一个整数数组 nums
中,需要找出第 k
个最大的元素。这里要注意,我们要找的是数组排序后的第 k
个最大元素,而不是第 k
个不同的元素。例如,对于数组 [3,2,1,5,6,4]
,当 k = 2
时,第 2 个最大的元素是 5。
二、解决思路
我们可以使用大顶堆排序算法来解决这个问题。大顶堆是一种完全二叉树,其中每个节点的值都大于或等于其子节点的值。通过构建大顶堆,我们可以将数组中的元素按照从大到小的顺序排列,然后取出第 k
个元素即可。
三、代码实现
/*** @param {number[]} nums* @param {number} k* @return {number}*/
var findKthLargest = function(nums, k) {let n = nums.length;// 以大顶堆为做法,其实堆就只是通过完全二叉树的性质,在数组中进行操作// 如果数组以 0 开头,那么节点 i 的左节点为 2 * i + 1,右节点为 2 * i + 2// max 表示维护的是 0 到 max 这部分的顺序,max 到 n - 1 这部分已经形成顺序了// i 表示维护的是以 i 为父节点,它和它子节点的大顶堆关系function heapify(max, i) {let lastMax = i;let lson = 2 * i + 1;let rson = 2 * i + 2;// 比较左子节点和父节点的大小,如果左子节点更大,则更新 lastMaxif (lson < max && nums[lson] > nums[lastMax]) {lastMax = lson;}// 比较右子节点和当前最大节点的大小,如果右子节点更大,则更新 lastMaxif (rson < max && nums[rson] > nums[lastMax]) {lastMax = rson;}// 如果 lastMax 不等于 i,说明需要交换父节点和最大子节点的位置if (lastMax != i) {let temp = nums[lastMax];nums[lastMax] = nums[i];nums[i] = temp;// 递归调用 heapify 函数,继续维护以 lastMax 为根节点的子树的大顶堆性质heapify(max, lastMax);}}// 大顶堆排序的入口function heap_sort() {// 首先要从最后一个非叶子节点开始建立大顶堆for (let i = Math.floor(n / 2 - 1); i >= 0; i--) {heapify(n, i);}// 然后呢,我们已经形成大顶堆了,现在要把他们完全排序// 怎么做呢,先把 [0] 与 [n - 1] 对调,这样 [n - 1] 的数就变成了最大的数// 接下来再维护 0 到 n - 2 之间的大顶堆,从堆顶 0 依次维护下去,数组 nums 就变成从小到大顺序的for (let i = n - 1; i >= 0; i--) {//这里是为了完整的堆排序,如果只是要获取第k大的//直接if(n==n-k-1) return nums[n-k]就行,无需再继续了let temp = nums[i];nums[i] = nums[0];nums[0] = temp;heapify(i, 0);}}heap_sort();console.log(nums);return nums[n - k];
};
四、代码详细解释
1. findKthLargest
函数
这个函数是整个算法的入口,它接收两个参数:nums
数组和 k
。首先,我们获取数组的长度 n
,然后调用 heap_sort
函数对数组进行排序,最后返回排序后数组的第 n - k
个元素,即为第 k
个最大的元素。
2. heapify
函数
这个函数用于维护以 i
为父节点的子树的大顶堆性质。具体步骤如下:
- 初始化
lastMax
为i
,表示当前最大节点为父节点。 - 计算左子节点的索引
lson = 2 * i + 1
和右子节点的索引rson = 2 * i + 2
。 - 比较左子节点和父节点的大小,如果左子节点更大,则更新
lastMax
为左子节点的索引。 - 比较右子节点和当前最大节点的大小,如果右子节点更大,则更新
lastMax
为右子节点的索引。 - 如果
lastMax
不等于i
,说明需要交换父节点和最大子节点的位置,然后递归调用heapify
函数,继续维护以lastMax
为根节点的子树的大顶堆性质。
3. heap_sort
函数
这个函数是大顶堆排序的入口,具体步骤如下:
- 构建大顶堆:从最后一个非叶子节点开始,依次调用
heapify
函数,将数组转换为大顶堆。最后一个非叶子节点的索引为Math.floor(n / 2 - 1)
。 - 排序:将堆顶元素(即数组的第一个元素)与数组的最后一个元素交换,然后将堆的大小减 1,再次调用
heapify
函数维护堆的性质。重复这个过程,直到堆的大小为 1,此时数组就已经按从小到大的顺序排序好了。