295. Find Median from Data Stream

原题：295. Find Median from Data Stream

这道题用的还是二分插入的思想，可见常见的算法模板还是要背得滚瓜烂熟啊同学们。。

source code

// Runtime: 288 ms, faster than 53.59% of JavaScript online submissions for Find Median from Data Stream.
// Memory Usage: 55.7 MB, less than 91.58% of JavaScript online submissions for Find Median from Data Stream.

/**
 * initialize your data structure here.
 */
var MedianFinder = function () {
  this.nums = [];
};

/**
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function (num) {
  let index;
  if (this.nums.length > 0) {
    let left = 0;
    let right = this.nums.length - 1;
    while (left + 1 < right) {
      let mid = left + ~~((right - left) / 2);
      if (this.nums[mid] >= num) {
        right = mid;
      } else {
        left = mid;
      }
    }

    if (num > this.nums[right]) {
      index = right + 1;
    } else if (num <= this.nums[left]) {
      index = left;
    } else {
      index = right;
    }
  } else {
    index = 0;
  }

  this.nums.splice(index, 0, num);
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function () {
  if (this.nums.length === 0) {
    return 0;
  }
  const mid = ~~(this.nums.length / 2);
  if (this.nums.length % 2 === 0) {
    return (this.nums[mid - 1] + this.nums[mid]) / 2;
  } else {
    return this.nums[mid];
  }
};

test cases:

test("test1", () => {
  const medianFinder = new MedianFinder();
  expect(medianFinder.findMedian()).toEqual(0);
});

test("test2", () => {
  const medianFinder = new MedianFinder();
  medianFinder.addNum(1);
  medianFinder.addNum(2);
  expect(medianFinder.findMedian()).toEqual(1.5);
});

test("test3", () => {
  const medianFinder = new MedianFinder();
  medianFinder.addNum(1);
  medianFinder.addNum(2);
  medianFinder.addNum(3);
  expect(medianFinder.findMedian()).toEqual(2);
});