网络异常，图片无法展示
|
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 复制代码
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 复制代码
提示：
1 <= k <= nums.length <= 104-104 <= nums[i] <= 104
sort 排序
本题要我们返回数组中第 k 大的值，最简单直接的方法就是将数组进行降序排列，然后返回第 k 个元素即可
代码如下：
var findKthLargest = function(nums, k) { // 降序排序 nums.sort((a,b) => b-a); // 返回排序后第k个元素 return nums[k-1] }; 复制代码
小顶堆
涉及到维护前 k 个最值的问题，都可以通过堆来解题
本题要维护的是前 k 个最大值，所以我们可以通过小顶堆来维护前 k 个最大值
最后堆顶元素就是第 k 个最大值
代码如下：
// 小顶堆 class MinHeap { constructor(k){ this.arr = []; this.size = 0; this.max = k; } // 插入操作 push(val){ this.arr.push(val); this.size++; // 自下向上平衡调整 if(this.size>1){ let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&this.arr[cur]<this.arr[parent]){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; } } // 如果堆中元素数量超过K个,弹出堆顶元素 if(this.size>this.max) this.pop(); } // 弹出操作 pop(){ this.arr[0] = this.arr.pop(); this.size--; // 自上向下平衡调整 let cur = 0, childl = 1,childr = 2; while( (childl<this.size&&this.arr[childl]<this.arr[cur]) || (childr<this.size&&this.arr[childr]<this.arr[cur]) ){ if(childr<this.size&&this.arr[childr]<this.arr[childl]){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl } childl = cur*2+1,childr = cur*2+2; } } // 返回堆顶元素 top(){ return this.arr[0] } } var findKthLargest = function(nums, k) { // 创建小顶堆实例 const heap = new MinHeap(k); // 循环输入数组 for(let i = 0;i<nums.length;i++){ // 当堆中数量小于k或者当前元素大于堆顶元素的时候，将当前元素插入堆中 if(heap.size<k||nums[i]>heap.top()){ heap.push(nums[i]) } } // 返回堆顶元素 return heap.top(); }; 复制代码
至此我们就完成了 leetcode-215-数组中的第K个最大元素
如有任何问题或建议，欢迎留言讨论！
