LeetCode(703)：找出数据流中的第K大元素

题目描述

实现思路一：堆

一种比较经典的做法是：维护一个只有K个元素的最小堆
这样，当前数据流中的第K大元素一定位于堆的顶部（数组头部）
当有新的数据进入时，将其与堆顶元素比较
若堆顶元素更大，则无视新的数据
若堆顶元素更小，则将其移出堆，并将新元素放入堆，再重新整理堆

---

在C++标准库中，堆可以使用PriorityQueue这个数据结构实现

实现思路二：数组splice

Javascript为数组提供了一种 splice方法
它可以向/从数组中添加/删除项目（会改变原始数组）
它可以接收3个参数

表示可以删除index处开始的0个或多个元素，并使用第三个参数 来替换被删除的元素

---

在每次接收新数据时
1、将新数据push入数组
2、对数据进行从大到小的排序
3、如果数组长度大于K，则删除索引大于等于K的所有元素
（使得每一次接收新数据后，数组的大小保持在K）
最后返回索引为K-1的元素即可

代码实现（Javascript)

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.k=k
    this.arr=new Array()
    if(nums.length>0){
        for(var i in nums){
            this.arr.push(nums[i])
        }
    }
    
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.arr.push(val)
    this.arr.sort(function(a,b){
        return b-a
    })
    if(this.arr.length>this.k){
        this.arr.splice(this.k, this.arr.length-this.k)
    }
    return this.arr[this.k-1]
};