查找数据流中的第K大元素

地址：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/，题号：703。
image.png

【解题思路】
这道题的思路是保存前K个最大值，每进来一个元素，判断这个元素跟堆顶元素（最小值）比较，如果大于最小值，就把堆顶值踢出，插入新值，然后维持整个堆的顺序。

  • 方法一：sorted 排序维持。对这K个值的堆进行sorted排序；
  • 方法二：最小堆维持。维持过程如下图。

image.png

二叉堆的写法比较麻烦，这里就不做展示，可以自行去LeetCode查看示例。

  1. var KthLargest = function(k, nums) {
  2.     this.k = k;
  3.     this.minHeap = [];        // 维持K个最大值的最小堆
  4.     var that = this;
  5.     nums.forEach((item)=> {
  6.         this.add(item);
  7.     })
  8. };
  10. KthLargest.prototype.add = function(val) {
  11.     let length = this.minHeap.length;
  12.     if(length < this.k){                    // 最小堆的长度是否已经超出K个值，没有直接插入
  13.         this.offer(val);
  14.     } else if(this.peek()<val) {    // 判断堆顶元素是否小于插入值，如果是，把堆顶元素踢出，插入新元素
  15.         this.minHeap.shift();
  16.         this.offer(val);
  17.     }
  18.     return this.peek();
  19. };
  21. /**
  22.     * 维持整个堆的顺序：
  23.       ①sorted
  24.     ②维持最小堆
  25.  */
  26. KthLargest.prototype.offer = function(val) { 
  27.       // 直接保存，然后sorted维持
  28.       this.priorityQueue.push(val);
  29.     this.priorityQueue.sort((a,b)=>a-b);
  31.       //splice维持
  32.     let pos=0;
  33.     let length = this.minHeap.length;
  34.     for(let i=0;i<=length;i++) {
  35.         if(this.minHeap[i]>=val) {
  36.             pos = i;
  37.             break;
  38.         } else {
  39.             pos = i;
  40.         }
  41.     }
  42.     this.minHeap.splice(pos, 0, val);
  43. }
  45. KthLargest.prototype.peek = function() {
  46.     return this.minHeap[0];
  47. }

那么，它们的时间复杂度是多少呢？
对于sorted排序方式，假设有n个元素进来，那么就是n次循环，然后对k个数进行排序，假设使用最佳的排序方式是快排，时间复杂度就是 O(N· klogK)；
对于二叉堆方式，同样是n个元素进来，那么就是n次循环，最优的情况是比堆顶元素少，那就是O(N·1)，最差的情况是对二叉堆进行调整，调整的时间复杂度是 O(N·logk)，那么取最差的情况logk，对比sorted排序还是有优势。

to be continue…