The title

703. The k-th large element in the data stream

Design a class that finds the KTH largest element in the data stream. Notice it’s the KTH largest element, not the KTH different element.

Please implement KthLargest class:

KthLargest(int k, int[] nums) uses the integer k and the integer stream nums to initialize the object. Int add(int val) Returns the KTH largest element in the current data stream after inserting val into the data stream nums.

Example:

Input:"KthLargest"."add"."add"."add"."add"."add"]
[[3[4.5.8.2]], [3], [5], [10], [9], [4] output: [null.4.5.5.8.8[largest, largest, largest, largestnew 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
Copy the code

Ideas:

Violent solution.

Declare an empty array, then loop through nums, advancing the first k large numbers into the array.

If k>nums, then nums can be pushed out. If k is less than nums, then you can just multiply k numbers.

And then, every time you get a number, you insert that number in the appropriate place in the array, and then you delete the top item.

I’m just making a judgment here, if the array is less than k, then I don’t have to delete it when I insert it

The code is as follows:

/ * * *@param {number} k
 * @param {number[]} nums* /
var KthLargest = function(k, nums) {
    this.index = k;
    let arr = [];
    let len =Math.min(k,nums.length);
    for(let i=0; i<len; i++){let maxIndex = 0
        for(let j=0; j<nums.length; j++){if(nums[j]>nums[maxIndex]){
                maxIndex = j
            }

        }
        arr.unshift(nums[maxIndex])
        nums.splice(maxIndex,1)}this.dataList = arr;
};

/ * * *@param {number} val
 * @return {number}* /
KthLargest.prototype.add = function(val) {
    let insertIndex = 0;
        for(let i=0; i<this.dataList.length; i++){if(val>this.dataList[i]){
            insertIndex = i+1;
            }else{
                break; }}if(insertIndex>0 || this.dataList.length < this.index){
            this.dataList.splice(insertIndex,0,val);
            if(this.dataList.length > this.index){
                this.dataList.shift(); }}return this.dataList[0]};Copy the code