This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

LeetCode 295. Median of data stream – JavaScript

Topic describes

The median is the number in the middle of an ordered list. If the list length is even, the median is the average of the middle two numbers.

Design a data structure that supports the following two operations:

  • void addNum(int num)Adds an integer from the data stream to the data structure.
  • double findMedian()Returns the current median for all elements.

Solution 1: Violence

Each time the median is fetched, all elements are sorted before the median is computed. The code is as follows:


var MedianFinder = function() {
  this.data = [];
};

MedianFinder.prototype.addNum = function(num) {
  this.data.push(num);
};

MedianFinder.prototype.findMedian = function() {
  const length = this.data.length;
  if(! length) {return null;
  }
  this.data.sort((a, b) = > a - b);

  const mid = Math.floor((length - 1) / 2);
  if (length % 2) {
    return this.data[mid];
  }
  return (this.data[mid] + this.data[mid + 1) /2;
};
Copy the code

You can also sort directly when you add elements. The time complexity is O(NlogN), but ac cannot be used.

Solution 2: binary search

You don’t need to reorder all the elements every time you add them. If you have always kept the elements in order, then when you add a new element, you just need to insert the element into the correct position, which can be found by “binary search”.

To keep the previous elements in order, place each new element in the right place.

The code implementation is as follows:

var MedianFinder = function() {
  this.data = [];
};

MedianFinder.prototype.addNum = function(num) {
  if (!this.data.length) {
    this.data.push(num);
    return;
  }

  let left = 0,
    right = this.data.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (this.data[mid] === num) {
      this.data.splice(mid, 0, num);
      return;
    } else if (this.data[mid] < num) {
      left = mid + 1;
    } else {
      right = mid - 1; }}this.data.splice(right + 1.0, num);
};

MedianFinder.prototype.findMedian = function() {
  const length = this.data.length;
  if(! length) {return null;
  }

  const mid = Math.floor((length - 1) / 2);
  if (length % 2) {
    return this.data[mid];
  }
  return (this.data[mid] + this.data[mid + 1) /2;
};
Copy the code

Binary lookup is order logN, moving elements is order N, so time is order N.

Solution 3: Maximum heap + minimum heap

For this kind of dynamic data, the heap is an excellent solution. Prepare two heaps:

  • Maximum heap: Stores the smaller half of the elements in the data stream
  • Minimum heap: Holds the larger half of the data flow

The two heaps need to be “balanced”. The balance here means that the size of the maximum heap = the size of the minimum heap, or the size of the maximum heap = the size of the minimum heap + 1.

When the findMedian query is called, the median is the top element of the largest heap, or (top element of the largest heap + top element of the smallest heap)/2

All that’s left is how do you balance the heap? The steps are as follows:

  • Let num enter maxHeap first
  • Take the top element of the maxHeap and place it in the minHeap
  • If at this timeThe size of the maximum heap < the size of the minimum heap, take the top element from the minHeap and place it in the maxHeap

Since there is no heap in JavaScript, implement it yourself. When implemented, only one copy of the heap code is required, and the comparison function that makes the decision in the heap is passed in from outside.

const defaultCmp = (x, y) = > x > y; // The default is maximum heap

const swap = (arr, i, j) = > ([arr[i], arr[j]] = [arr[j], arr[i]]);

class Heap {
  /** * default is maximum heap *@param {Function} cmp* /
  constructor(cmp = defaultCmp) {
    this.container = [];
    this.cmp = cmp;
  }

  insert(data) {
    const { container, cmp } = this;

    container.push(data);
    let index = container.length - 1;
    while (index) {
      let parent = Math.floor((index - 1) / 2);
      if(! cmp(container[index], container[parent])) {return; } swap(container, index, parent); index = parent; }}extract() {
    const { container, cmp } = this;
    if(! container.length) {return null;
    }

    swap(container, 0, container.length - 1);
    const res = container.pop();
    const length = container.length;
    let index = 0,
      exchange = index * 2 + 1;

    while (exchange < length) {
      If there is a right node, and the value of the right node is greater than the value of the left node
      let right = index * 2 + 2;
      if (right < length && cmp(container[right], container[exchange])) {
        exchange = right;
      }
      if(! cmp(container[exchange], container[index])) {break;
      }
      swap(container, exchange, index);
      index = exchange;
      exchange = index * 2 + 1;
    }

    return res;
  }

  top() {
    if (this.container.length) return this.container[0];
    return null; }}Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤