「这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战」
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
示例：
输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出： [null, 4, 5, 5, 8, 8] 解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8 复制代码
提示：
1 <= k <= 1040 <= nums.length <= 104- -
104 <= nums[i] <= 104 - -
104 <= val <= 104 - 最多调用
add方法104次 - 题目数据保证，在查找第
k大元素时，数组中至少有k个元素
题解1. sort排序
本题我们可以想到最简单的办法就是将数组进行从大到小排序，每次 add 将 val 插入 nums 数组，并对数组重新进行排序，返回 nums[k-1] 即可。代码如下：
/** * @param {number} k * @param {number[]} nums */ var KthLargest = function(k, nums) { this.k = k; this.nums = nums; this.nums.sort((a,b) => b-a) }; /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function(val) { this.nums.push(val); this.nums.sort((a,b)=> b-a) return this.nums[this.k-1] }; 复制代码
这种方法可以通过本题，但是耗时在 3000ms 左右，是很低效的。
接下来我们对上面代码进行一下优化。
首先，我们根据题意可得我们要找到的是数据流中的第 k 大元素，所以当我们从大到小将数组排序后，数据中第 k 个元素之后的元素对我们是没有意义的，但是这些元素存在在数组中，在我们 add(val) 后再次进行 sort 的时候是很影响效率的，所以我们优化我们的代码如下：
/** * @param {number} k * @param {number[]} nums */ var KthLargest = function(k, nums) { this.k = k; this.nums = nums; this.handle(); }; KthLargest.prototype.handle = function(){ this.nums.sort((a,b)=> b-a) // 维护数组长度 while(this.nums.length>this.k) this.nums.pop(); } /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function(val) { this.nums.push(val); this.handle(); return this.nums[this.k-1] }; 复制代码
这一版代码我这里提交耗时 1800ms 左右,可以看到相对于上一版代码是有一个提升的
接下来我们再思考一个问题，当我们要 add 的 val 小于我们当前的 nums[k-1] 的时候，其实我们是不需要将它添加到 nums 数组中的，所以我们优化代码如下：
/** * @param {number} k * @param {number[]} nums */ var KthLargest = function(k, nums) { this.k = k; this.nums = nums; this.handle(); }; KthLargest.prototype.handle = function(val){ // 当数组长度有K个元素且新插入的值小于第K个元素，不进行处理 if(val!==undefined&&this.nums.length>=this.k&&val<this.nums[this.k-1]) return; this.nums.push(val); this.nums.sort((a,b)=> b-a) // 维护数组长度 while(this.nums.length>this.k) this.nums.pop(); } /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function(val) { this.handle(val); return this.nums[this.k-1] }; 复制代码
这一版代码我这里提交耗时 1200ms 左右,可以看到相对于上一版代码是有一个提升的。
至此我们通过 sort排序 维护一个从大到小的 k 个最大值的有序数组完成了本题，但是我们优化了两版之后的代码执行耗时还是需要 1200ms 左右，可见这种解题方法不是一个比较高效的解法。
题解2. 二分插入
上面的 sort排序 方法其实很大的开销是在每次插入 val 后都需要对数组重新进行排序，那我们每次将 val 值插入到我们有序数组的合适位置，是不是就可以避免这种每次的排序了呢？
我们再思考一个问题，这里我们要将新的 val 值插入到有序数组的合适位置，这个操作一定是要比 sort排序 的效率要高的，才能保证我们的这种解法比 sort排序 解法更优化，我这里就想到了可以通过 二分查找 来找到将 val 值插入到有序数组的合适位置，如果你对 二分查找 不太熟悉，可以看一下我之前的 《leetcode-35-搜索插入位置》
整理一下二分插入的解题思路：
- 初始化的时候对
nums数组进行排序 add(val)时通过二分查找找到该值在有序数组中的合适插入位置进行插入，并维护nums数组的数量- 返回
nums[k-1]即可
代码如下：
/** * @param {number} k * @param {number[]} nums */ var KthLargest = function(k, nums) { this.k = k; this.nums = nums; this.nums.sort((a,b)=> b-a) }; KthLargest.prototype.handle = function(val){ // 当数组长度有K个元素且新插入的值小于第K个元素，不进行处理 if(val!==undefined&&this.nums.length>=this.k&&val<this.nums[this.k-1]) return; // 特判数组长度为1的情况 if(this.nums.length === 1){ if(this.nums[0]>val) this.nums.push(val) else this.nums.unshift(val) }else{ // 二分查找合适的插入位置 let l = 0,r = this.nums.length-1; while(l<r){ const mid = (l+r) >> 1; if(this.nums[mid]>val) l = mid+1; else r = mid; } this.nums.splice(l,0,val) } // 维护数组长度 while(this.nums.length>this.k) this.nums.pop(); } /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function(val) { this.handle(val); return this.nums[this.k-1] }; 复制代码
这一版代码我这里提交耗时 130ms 左右，基本达到了一个最优解的耗时
题解3. 小顶堆维护K的最大数
这里我们再分享一种在数据结构中常用来维护最值的一种数据结构 => 堆
堆是一种基于完全二叉树的数据结构，它的性质是每一个三元组的最值在根节点 上图是一个大顶堆，所以每一个节点和它的左子树、右子树组成的三元组中，最大的值一定在根节点，又因为整个堆的堆顶元素是所有其余节点的祖先节点，所以整个堆的最值在堆顶元素。
在我们实际的程序中，是使用数组来存储堆这种数据结构的，那么堆中每一个节点对应数组中的小标就是上图用黑色数字标记的值，每一层依次从左到右的放入数组，即为上图右侧的数组。
通过上图我们可以看到每一个节点的左子树的下标等于根节点下标 n*2+1,右子树下标等于根节点下标 n*2+2
根据堆的如上性质，如果我们通过小顶堆，来维护数据流中的前 k 个最大的元素，此时，堆顶的元素，就是数据流中的第 k 大元素。
接下来我们说一下堆的插入操作和弹出操作
堆的插入操作
堆的插入操作对应我们的数组就是在数组末尾插入一个值
此时以途中的大顶堆为例，我们需要判断新插入的值在它对应的三元组中是否大于根节点的值，如果新插入的值大于根节点的值，则和根节点互换位置，不断重复此过程，知道该值小于它的根节点或者该值成为了堆顶元素
如此就完成了堆的插入向上调整
堆的弹出操作
堆的弹出操作指将堆顶元素弹出堆，此时堆顶为空，我们将数组的末尾元素放到堆顶，然后在数组中删除末尾元素
此时之前数组中的末尾元素放在堆顶，肯定是违反了堆的性质的，所以我们要进行向下调整
判断该值是否是当前三元组中的最大值，如果不是，找到当前三元组的最大值，和堆顶元素互换位置，此时堆顶元素来到了第二层，重复以上过程，知道该值是当前三元组的最大值或者该值已经到了我们堆的最底层
如此就完成了堆的弹出向下调整
最后，我们通过手写一个小顶堆，完成本题，代码如下：
/** * @param {number} k * @param {number[]} nums */ var KthLargest = function(k, nums) { this.heap = new MinHeap(k); for(let i = 0;i<nums.length;i++){ this.heap.push(nums[i]) } }; /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function(val) { this.heap.push(val); return this.heap.top(); }; class MinHeap { constructor(max){ this.arr = []; this.size = 0; this.max = max; } // 插入 push(val){ if(this.size>=this.max&&val<this.top()) return; this.arr.push(val); this.size++; // 插入操作后向上调整 if(this.size>1){ let cur =this.size-1; let parent = (cur-1) >> 1; while(cur>0&&this.arr[parent]>this.arr[cur]){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent; parent = (cur-1) >> 1; } } // 维护最大个数 while(this.size>this.max) this.pop(); } // 弹出 pop(){ if(this.empty()) return; this.arr[0] = this.arr.pop(); this.size--; // 弹出操作后向下调整 let cur = 0, childl = cur*2+1, childr = cur*2+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] } // 判空 empty(){ return this.size === 0 } } 复制代码
这一版代码我这里提交耗时 130ms 左右，同样达到了一个最优解的耗时
至此，我们通过三种方式完成了leetcode-703-数据流中的第K大元素
如有任何问题或建议，欢迎留言讨论！
