给定整数数组 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
1 class MinHeap { 2 constructor(){ 3 this.heap = []; 4 } 5 swap(i1, i2){ 6 const temp = this.heap[i1]; 7 this.heap[i1] = this.heap[i2]; 8 this.heap[i2] = temp; 9 } 10 getParentIndex(i){ //获取父节点的值 11 return (i-1) >> 1; //二进制右移相当于除以2 12 } 13 getLeftIndex(i) { //获取左结点 14 return i * 2 + 1; 15 } 16 getRightIndex(i) { //获取右结点 17 return i * 2 + 2; 18 } 19 20 shiftUp(index){ //需要让父节点不断小于它的子节点 21 if(index == 0){ return; } //如果已经是根结点了就不用找了 22 const parentIndex = this.getParentIndex(index); 23 if(this.heap[parentIndex] > this.heap[index]){ 24 this.swap(parentIndex, index); //如果父节点的值大于子节点则进行交换 25 this.shiftUp(parentIndex) 26 } 27 } 28 insert(value){ //插入,添加的方法 29 this.heap.push(value); 30 this.shiftUp(this.heap.length - 1); //shiftUp就是上移操作,接收参数是上移时的下标 31 } 32 shiftDown(index){ //下移节点,直到子节点都大于当前节点的值 33 // 需要获取它的左右子节点 34 const leftIndex = this.getLeftIndex(index); 35 const rightIndex = this.getRightIndex(index); 36 if(this.heap[leftIndex] < this.heap[index]){ //小顶堆,父节点小于子节点 37 this.swap(leftIndex, index); 38 this.shiftDown(leftIndex); //递归,直到找到合适的位置 39 } 40 if(this.heap[rightIndex] < this.heap[index]){ //小顶堆,父节点小于子节点 41 this.swap(rightIndex, index); 42 this.shiftDown(rightIndex); //递归,直到找到合适的位置 43 } 44 } 45 46 pop(){ //下移方法 47 this.heap[0] = this.heap.pop(); // 把数组的最后一位转移到头部,相当于变相删除堆顶 48 this.shiftDown(0); //传什么下标,就对那个进行下移操作 49 } 50 peek(){ //获取堆顶,返回数组的头部 51 return this.heap[0]; 52 } 53 size(){ // 获取堆的大小 54 return this.heap.length; 55 } 56 } 57 /** 58 * @param {number[]} nums 59 * @param {number} k 60 * @return {number} 61 */ 62 var findKthLargest = function(nums, k) { 63 const h = new MinHeap(); //构建一个最小堆 64 nums.forEach(n => { 65 h.insert(n); 66 if(h.size() > k) { //大于堆的个数,就把堆顶删除 67 h.pop(); 68 } 69 }) 70 return h.peek(); //所以都插入完成之后,堆顶就是要的元素 71 };