【leetcode】堆习题

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}
}

LCR 159. 库存管理 III（计数排序）
仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。
示例 1：
输入：stock = [2,5,7,4], cnt = 1
输出：[2]
示例 2：
输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]
提示：
0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000

/*** @param {number[]} stock* @param {number} cnt* @return {number[]}*/// 原生API
var inventoryManagement = function(stock, cnt) {return stock.sort((a,b) => a-b).slice(0, cnt)
};// 计数排序 用空间换时间
var inventoryManagement = function(stock, cnt) {return countingSort(stock, cnt, 10000)
};
let countingSort = (arr, k, maxValue) => {let bucket = new Array(maxValue),sortedIndex = 0,arrLen = arr.lengthbucketLength = maxValue// 生成 bucket. 示例：stock = [2,5,7,4]，则 bucket = [0, 0, 1, 0, 1, 1, 0, 1]for (let i = 0; i < arrLen; i++) {if (!bucket[arr[i]]) {bucket[arr[i]] = 0}bucket[arr[i]]++}let res = []for (let j = 0; j < bucketLength; j++) {while (bucket[j]-- > 0 && sortedIndex < k) {res[sortedIndex++] = j}if (sortedIndex === k) {break}}return res
}

347.前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的