电子商务与网络营销教案_南京app开发外包公司_优化网站怎么真实点击_怎样优化网站排名靠前

215.数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 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 <= 105
-104 <= nums[i] <= 104

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var findKthLargest = function(nums, k) {let arr = new MinHeap()nums.forEach(item => {arr.insert(item)if (arr.size() > k) {arr.pop()}})return arr.peek()
};class MinHeap {constructor() {this.heap = []}// 换位置swap(i1, i2) {let temp = this.heap[i1]this.heap[i1] = this.heap[i2]this.heap[i2] = temp}// 找到父节点getParentIndex(index) {return Math.floor((index - 1) / 2)}// 上（前）移操作up(index) {if (index === 0) returnconst parentIndex = this.getParentIndex(index)if (this.heap[parentIndex] > this.heap[index] ) {this.swap( parentIndex, index )this.up(parentIndex)}}// 找到左侧子节点getLeftIndex(index) {return index * 2 + 1}// 找到右侧子节点getRigthIndex(index) {return index * 2 + 2}// 下（后）移操作down(index) {const leftIndex = this.getLeftIndex(index)const rightIndex = this.getRigthIndex(index)if (this.heap[leftIndex] < this.heap[index]) {this.swap(leftIndex, index)this.down(leftIndex)}if (this.heap[rightIndex] < this.heap[index]) {this.swap(rightIndex, index)this.down(rightIndex)}}// 添加元素insert( value ) {this.heap.push(value)this.up( this.heap.length-1 )}// 删除堆顶pop() {this.heap[0] = this.heap.pop()this.down(0)}// 获取堆顶peek() {return this.heap[0]}// 获取堆长度size() {return this.heap.length}
}