HHot 100C++ 图解

295. 数据流的中位数

一句话套路对顶堆:大顶装小半、小顶装大半

题目描述

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

  • 例如 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

思路

空间O(n)

思路

对顶堆。lo 是大顶堆(较小的一半),hi 是小顶堆(较大的一半),

维持不变式

lo.size() == hi.size() 或 lo.size() == hi.size() + 1。

中位数

总数奇数 -> lo 堆顶;偶数 -> 两个堆顶平均。

为什么不用排序?插入是 O(n);堆让 addNum O(log n)、findMedian O(1)。

延伸

Q480 滑动窗口中位数要能删除任意元素 -> 懒删除(延迟删除)+ 两个堆。

图解

两个堆:左=大顶堆存较小的一半,右=小顶堆存较大的一半,保持左.size ≤ 右.size 且相差 ≤ 1。所有数始终分成两段,中位数就是左堆顶 或 (左顶+右顶)/2。

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/13_heap.cpp23 行
namespace lc0295 {
class MedianFinder {
 public:
  void addNum(int num) {
    lo.push(num);        // 先进大顶堆,再把它的「最大值」交给右半 —— 保证左半全部 <= 右半
    hi.push(lo.top());   // 把大顶堆最大值挪到右半,维持 lo <= hi
    lo.pop();
    if (hi.size() > lo.size()) {  // 保持 lo 不少于 hi
      lo.push(hi.top());
      hi.pop();
    }
  }

  double findMedian() const {
    if (lo.size() > hi.size()) return lo.top();
    return (static_cast<double>(lo.top()) + hi.top()) / 2.0;
  }

 private:
  priority_queue<int> lo;                                 // 大顶堆:较小的一半
  priority_queue<int, vector<int>, greater<int>> hi;      // 小顶堆:较大的一半
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q295_median_finder17 行
lc0295::MedianFinder mf;
mf.addNum(1);
CHECK_NEAR(mf.findMedian(), 1.0, 1e-9);
mf.addNum(2);
CHECK_NEAR(mf.findMedian(), 1.5, 1e-9);
mf.addNum(3);
CHECK_NEAR(mf.findMedian(), 2.0, 1e-9);
mf.addNum(4);
CHECK_NEAR(mf.findMedian(), 2.5, 1e-9);
mf.addNum(5);
CHECK_NEAR(mf.findMedian(), 3.0, 1e-9);
lc0295::MedianFinder m2;
m2.addNum(-1);
m2.addNum(-2);
CHECK_NEAR(m2.findMedian(), -1.5, 1e-9);  // 负数
m2.addNum(-3);
CHECK_NEAR(m2.findMedian(), -2.0, 1e-9);

↑↓ 选择↵ 打开/ 随时唤起