295.数据流的中位数

数据流的中位数

设计一个支持以下两种操作的数据结构：addNum(int num) 从数据流中添加一个整数到数据结构中；findMedian() 返回目前所有元素的中位数。

解析

使用排序数组模拟（JS 无内置堆，可用二分插入保持有序）。

var MedianFinder = function () { this.arr = []; };
MedianFinder.prototype.addNum = function (num) {
  let lo = 0, hi = this.arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (this.arr[mid] < num) lo = mid + 1; else hi = mid;
  }
  this.arr.splice(lo, 0, num);
};
MedianFinder.prototype.findMedian = function () {
  const n = this.arr.length;
  const mid = n >> 1;
  return n % 2 ? this.arr[mid] : (this.arr[mid - 1] + this.arr[mid]) / 2;
};