The KTH large element in a data stream

The title

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]

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

Tip:

1 <= k <= 104 0 <= nums.length <= 104-104 <= nums[I] <= 104-104 <= val <= 104 There are at least k elements in the array

Tip:

1 <= stones.length <= 30

1 <= stones[i] <= 1000

Analysis of the

  • First we can initializeKthLargest, sort the array to facilitate subsequent executionadd
  • throughspliceMethod to add elements when argument twohowmanyfor0Is the add operation

Pseudo code

  • Initialize a variablearrSort the variables from large to small and initialize themkvalue
  • The defaultposInsert to the end of the array
  • Find by traversingposInsert position, since we’ve already done the order from large to small, we just need to determine what value we want to addvalGreater than the current value to find where to insertpos
  • Returns the KTH element of the data stream based on the inserted arraythis.arr[this.k-1]

Code implementation

/** * @param {number} k * @param {number[]} nums */ var KthLargest = function(k, nums) { this.arr = nums.sort((a,b) => b - a) this.k = k }; /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function(val) { let pos = this.arr.length for(let i = 0; i < pos ; i++){ if(val >= this.arr[i]){ pos = i break } } this.minHeap.splice(pos,0,val) return this.arr[this.k-1] }; /** * Your KthLargest object will be instantiated and called as such: * var obj = new KthLargest(k, nums) * var param_1 = obj.add(val) */Copy the code