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

First, conventional solution:

In order to find the KthLargest element in the data stream, we need to sort it first, implement the construction of KthLargest class, and sort it

var KthLargest = function(k, nums) {
    for (let j = 0; j < nums.length - 1; j++) {
        for (let i = 0; i < nums.length - 1; i++) {
        let current = nums[i]
        let next = nums[i + 1]
        if (current > next) {
            let temp = nums[i]
            nums[i] = nums[i + 1]
            nums[i + 1] = temp
        }
    }
    
  }
    this.k = k
    this.nums = nums

};
Copy the code

The add() method is used to push the data to the end of the data stream, and the insert sort is done again, just for the last element.

KthLargest.prototype.add = function(val) { this.nums.push(val) let insertIndex = this.nums.length - 2 while (insertIndex  >= 0 && this.nums[insertIndex] > val) { this.nums[insertIndex + 1] = this.nums[insertIndex] insertIndex-- } this.nums[insertIndex + 1] = val return this.nums[this.nums.length - this.k] };Copy the code

The insertion sort algorithm will not be described in detail, please refer to the previous article: Insertion sort

Since the code is sorted from smallest to largest, the maximum data is returned in the data length – insert subscript.

Complete code:

/** * @param {number} k * @param {number[]} nums */ var KthLargest = function(k, nums) { for (let j = 0; j < nums.length - 1; j++) { for (let i = 0; i < nums.length - 1; i++) { let current = nums[i] let next = nums[i + 1] if (current > next) { let temp = nums[i] nums[i] = nums[i + 1] nums[i + 1] = temp } } } this.k = k this.nums = nums }; /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function(val) { this.nums.push(val) let insertIndex = this.nums.length - 2 while (insertIndex >= 0 && this.nums[insertIndex] > val) { this.nums[insertIndex + 1]  = this.nums[insertIndex] insertIndex-- } this.nums[insertIndex + 1] = val return this.nums[this.nums.length - this.k] };Copy the code

Results:

Two, JS quick solution:

Due to the characteristics of THE JS API, you can use the UNIQUE JS API under the condition that the idea remains unchanged, to achieve the purpose of quick and convenient problem solving.

/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
  this.nums = nums.sort((a, b) => b - a)
  this.k = k
};

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

Copy the code

Results:

Compare the two solutions: although the JS API code is very small, but the memory consumption is large, and the execution time is nearly 9 times of the conventional solution, if in practical problems, need to consider the choice!