题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：

输入：
[“MedianFinder”,”addNum”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：

输入：
[“MedianFinder”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

最多会对 addNum、findMedian 进行 50000 次调用。
注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

js 可以直接用二分插入，再取中位数。一般做法利用大小堆做。大小堆js实现比较复杂。

  1. /**
  2.  * initialize your data structure here.
  3.  */
  4. var MedianFinder = function() {
  5.     this.arr = [];
  6. };
  8. /** 
  9.  * @param {number} num
  10.  * @return {void}
  11.  */
  12. MedianFinder.prototype.addNum = function(num) {
  13.     let arr = this.arr;
  14.     let len = arr.length;
  15.     let left = 0;
  16.     let right = len - 1;
  17.     while (left <= right) {
  18.         let mid = ~~((left + right) / 2);
  19.         if (arr[mid] === num) {
  20.             arr.splice(mid, 0, num);
  21.             // 找到并加入后直接返回
  22.             return ; 
  23.         } else if (arr[mid] > num) {
  24.             right = mid - 1;
  25.         } else {
  26.             left = mid + 1;
  27.         }
  28.     }
  29.     arr.splice(right + 1, 0, num);
  30. };
  32. /**
  33.  * @return {number}
  34.  */
  35. MedianFinder.prototype.findMedian = function() {
  36.     let len = this.arr.length;
  37.     let mid = ~~(len / 2);
  38.     if (len % 2 === 0) {
  39.         return (this.arr[mid - 1] + this.arr[mid]) / 2;
  40.     }
  41.     return this.arr[mid];
  42. };
  44. /**
  45.  * Your MedianFinder object will be instantiated and called as such:
  46.  * var obj = new MedianFinder()
  47.  * obj.addNum(num)
  48.  * var param_2 = obj.findMedian()
  49.  */