数据流的中位数

题面

中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。

• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0]

解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0

提示:

• -105 <= num <= 105
• 在调用 findMedian 之前，数据结构中至少有一个元素 最多 5 104 次调用 addNum 和 findMedian

分析

• 可以使用两个堆来维护，其中大顶堆维护中位数左侧的元素，小顶堆维护右侧的元素

• 当要加入一个新元素时，要尽量维护两个堆的大小尽量相等，其中大顶堆比小顶堆可以多一个元素

• 如果当前 left 的大小和 right 的大小相等：

  • 如果添加的数字 num 比较大，比如添加 7，那么把 7 加到 right 中。现在 left 比 right 少 1 个数，不符合前文的规定，所以必须把 right 的最小值从 right 中去掉，添加到 left 中。如此操作后，可以保证 left 的所有元素都小于等于 right 的所有元素。
  • 如果添加的数字 num 比较小，比如添加 0，那么把 0 加到 left 中。
  • 这两种情况可以合并：无论 num 是大是小，都可以先把 num 加到 right 中，然后把 right 的最小值从 right 中去掉，并添加到 left 中。

• 如果当前 left 比 right 多 1 个数：

  • 如果添加的数字 num 比较大，比如添加 7，那么把 7 加到 right 中。
  • 如果添加的数字 num 比较小，比如添加 0，那么把 0 加到 left 中。现在 left 比 right 多 2 个数，不符合前文的规定，所以必须把 left 的最大值从 left 中去掉，添加到 right 中。如此操作后，可以保证 left 的所有元素都小于等于 right 的所有元素。
  • 这两种情况可以合并：无论 num 是大是小，都可以先把 num 加到 left 中，然后把 left 的最大值从 left 中去掉，并添加到 right 中。

• 代码实现

  class MedianFinder {
      priority_queue<int> left; // 最大堆
      priority_queue<int, vector<int>, greater<>> right; // 最小堆
  
  public:
      void addNum(int num) {
          if (left.size() == right.size()) {
              right.push(num);
              left.push(right.top());
              right.pop();
          } else {
              left.push(num);
              right.push(left.top());
              left.pop();
          }
      }
  
      double findMedian() {
          if (left.size() > right.size()) {
              return left.top();
          }
          return (left.top() + right.top()) / 2.0;
      }
  };