数组中的第K个最大元素
数组中的第K个最大元素
在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
示例
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4题解
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(arr, k) {
var adjustHeap = function(arr, i, n) {
for(let k=2*i+1; k<n; k=2*k+1){
let parent = arr[i];
if(k+1 < n && arr[k] < arr[k+1]) ++k;
if(parent < arr[k]){
[arr[i], arr[k]] = [arr[k], arr[i]];
i = k;
}else{
break;
}
}
}
var n = arr.length;
for(let i = Math.floor(n/2-1); i>=0; --i) adjustHeap(arr, i, n);
var target = 0;
for(let i=n-1; i>=n-k; --i){
target = arr[0];
if(i-1>=n-k){
[arr[0], arr[i]] = [arr[i], arr[0]];
adjustHeap(arr, 0, i);
}
}
return target;
};思路
采用大顶堆的数据结构解决问题，大顶堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值并且为完全二叉树，首先定义adjustHeap函数左调整堆使用，首先以i作为双亲元素的下标，以k作为左孩子的下标，当右孩子存在时判断右孩子是否大于左孩子，大于左孩子则将k作为右孩子的指向下标，然后判断双亲值与k指向的孩子的节点值的大小，如果孩子值大于双亲值则交换，并且以k作为双亲节点沿着路径继续向下调整，否则就结束本次循环，然后定义n作为数组长度，之后将堆中每个作为双亲节点的子树进行调整，使整个树符合大顶堆的特征，之后进行k次循环，由于是大顶堆且已调整完成将顶堆的顶值也就是最大值取出赋值给target，之后判断是否需要进一步调整，如果需要则交换顶端值与最后一个值，然后调整顶堆符合大顶堆的条件，同样取出顶堆最大值，取出k次即可完成。
每日一题
https://github.com/WindrunnerMax/EveryDay参考
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录