烟台酒店网站建设,自我介绍网页,温州seo公司,关键词seo优化215.数组中的第K个最大元素 给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。 请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 输…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 个高频元素的集合是唯一的
