This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

108. Kth-largest element-in-a-stream (kTH-largest element-in-a-stream)

The label

  • The heap
  • Priority queue
  • Simple (for languages with priority queue apis)

The title

Leetcode portal

Let’s just open leetCode.

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.

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

The basic idea

This problem is relatively easy to implement in other languages, JS to go around a little bit, using the priority queue idea, one of the ways to implement is heap

Since the data stream is changing, there will be numbers added in, but we always care about the first k large number, so we create a small top heap, the top of which is the KTH large number, and we just need to maintain the heap (length K).

Key to the add method:

  • When heap array lengthLess than kWhen, the new number from the arrayAt the end of the push.Float up to the parent element, to its proper position.
  • When heap array lengthGreater than or equal to kWhen, if the new numberGreater than the top of the stack elementAnd use itReplace the pile top.Sinking compared to the left and right childrenAnd finally switch to the appropriate position.

The last one is the first k number, and the top of the heap is the KTH number, because it’s the small top heap, which is the minimum of the heap.

Writing implement

class MinHeap {

  constructor(k, nums) {
    // Priority queue array, heap is a binary small top heap for easy calculation
    this.heap = [];
    this.k = k;
  }

  // Heap insertion
  add(val) {
    // If the minimum heap is not full, enter the heap first
    if (this.heap.length < this.k) {
    	// At the end of the array index = this.heap.length - 1
    	this.heap.push(val)
    	// Float to set the small top stack
    	this.up(this.heap.length - 1)}else if (val > this.heap[0]) {
    	// If this element is larger than the top of the heap, replace the top, because the top was the KTH largest,
    	// Now there is a bigger one, and he is the k + 1 big one, which is pushed out of the small top heap
    	this.heap[0] = val
    	this.down(0)}Otherwise, the element is discarded, because it is smaller than the minimum heap top, indicating that the first k elements cannot be filled
  }

  // Float from bottom to top
  up(idx) {
    // Since it is a binary heap, calculate the index = parent of the heap's parent node
    let parent = Math.floor((idx - 1) / 2);
    // If the parent node is larger than the IDX node, the node floats
    if (parent >= 0 && this.heap[parent] > this.heap[idx]) {
    // Switch the parent and idx positions
      [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
      // Continue to float up recursively
      this.up(parent); }}// By the top comparison sink operation
  down(idx) {
    let tempIdx = idx;
    // Left child idx = idx * 2 + 1
    let left = idx * 2 + 1;
    // Compare the left child, if it is older than the left child, change position
    if (left < this.heap.length && this.heap[left] < this.heap[tempIdx]) {
      tempIdx = left;
    }
    let right = idx * 2 + 2;
    // Same thing on the right
    if (right < this.heap.length && this.heap[right] < this.heap[tempIdx]) {
      tempIdx = right;
    }
    // The tempIdx is now the smaller of the left and right children, or both are larger than the root (the tempIdx is still idx)
    if(tempIdx ! == idx) { [this.heap[tempIdx], this.heap[idx]] = [this.heap[idx], this.heap[tempIdx]];
      // Continue the recursion
      this.down(tempIdx); }}}// Declare global variables
let minHeap = []

var KthLargest = function (k, nums) {
  // create a small top heap to assign to the global variable
  minHeap = new MinHeap(k, nums);
  // All elements are added to the minimum heap
  for (let i = 0; i < nums.length; i++) { minHeap.add(nums[i]); }}; KthLargest.prototype.add =function (val) {
  minHeap.add(val);
  // return the top element of the heap, the KTH element
  return minHeap.heap[0];
};

let kthLargest = new KthLargest(3[8.4.5.2]);
console.log(kthLargest.add(3)) // return 4
console.log(kthLargest.add(5)) // return 5
console.log(kthLargest.add(10)) // return 5
console.log(kthLargest.add(9)) // return 8
console.log(kthLargest.add(4)) // return 8
Copy the code

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference