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 题解
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; // 小顶堆:较大的一半
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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);