No matter what everyone in the world says, I think my feelings are right. No matter what other people think, I never break my rhythm. Like things naturally can insist, do not like how also can not long.

LeetCode: the original address

Topic request

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: 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 8Copy the code

Tip:

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • The Add method can be called up to 104 times
  • The problem data guarantees that there are at least K elements in the array when looking for the KTH largest element

Train of thought

This is a variable array, we’re adding numbers, but we’re always interested in the first k numbers, so we maintain a minimum heap to hold the first k numbers.

Maintain an heap array.

When the heap array is k short, the new number is pushed from the end of the array, performing a “float up” to swap to its proper place. When the heap array is k long enough, if the new number is larger than the top of the stack, it replaces the top of the heap, performing “sink” to swap to the appropriate place. Finally, the heap array holds the first K largest number, and the top of the heap is the KTH largest number, the smallest element in the smallest heap.

code

class MinHeap { constructor(k, nums) { this.heap = []; this.k = k; } add(num) { if (this.heap.length < this.k) { this.heap.push(num); this.up(this.heap.length - 1); } else if (num > this.heap[0]) { this.heap[0] = num; this.down(0); } } up(i) { while (i > 0) { const parent = (i - 1) >> 1; if (this.heap[parent] > this.heap[i]) { [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]]; i = parent; } else { break; } } } down(i) { while (2 * i + 1 < this.heap.length) { let child = 2 * i + 1; if (child + 1 < this.heap.length && this.heap[child + 1] < this.heap[child]) { child++; } if (this.heap[i] > this.heap[child]) { [this.heap[child], this.heap[i]] = [this.heap[i], this.heap[child]]; i = child; } else { break; } } } } var KthLargest = function (k, nums) { this.heap = new MinHeap(k, nums); for (let i = 0; i < nums.length; i++) { this.heap.add(nums[i]); }}; KthLargest.prototype.add = function (val) { this.heap.add(val); return this.heap.heap[0]; };Copy the code