0295. Find Median from Data Stream
=================================
题目信息
--------
:题号: 0295
:难度: Hard
:主题: 数据流、对象设计、中位数、跨调用状态
:原题: `LeetCode 0295 `_
:重点: 新数据持续加入、奇偶数量对应不同中位数定义、查询必须覆盖此前全部元素
题目重述
--------
实现 ``MedianFinder`` 类,用于持续接收整数并查询当前数据集合的中位数:
* ``MedianFinder()`` 创建一个尚未加入数据的对象;
* ``addNum(num)`` 把整数 ``num`` 加入当前数据流;
* ``findMedian()`` 返回截至当前已经加入的全部整数的中位数。
把已有元素按非递减顺序排列后,元素数量为奇数时,中位数是正中间的元素;数量为偶数时,中位数是中间两个元素的算术平均值,因此返回类型为浮点数。``num`` 位于 ``[-10^5, 10^5]``,题目保证调用 ``findMedian`` 前至少加入过一个元素。``addNum`` 与 ``findMedian`` 的总调用次数不超过 ``5 * 10^4``,对象必须在不同调用之间保留此前全部数据的逻辑状态。
自建示例
--------
数据量从偶数变为奇数:
.. code-block:: text
操作:addNum(5), addNum(1), findMedian(), addNum(9), findMedian()
输出:3.0, 5.0
解释:前两项排序后为 [1,5],中位数是 (1+5)/2=3;加入 9 后为 [1,5,9],中位数是 5。
继续加入负数:
.. code-block:: text
操作:addNum(5), addNum(1), addNum(9), addNum(-3), findMedian()
输出:3.0
解释:四个数排序后为 [-3,1,5,9],中间两个数是 1 和 5,平均值为 3。
用两个堆维护排序中线
--------------------
把数据分成两个部分:最大堆 ``lower`` 保存较小的一半,最小堆 ``upper`` 保存较大的一半,保持:
* ``lower`` 的元素数量等于或比 ``upper`` 多 1;
* ``lower.top() <= upper.top()``(两堆都非空时)。
加入新数时,若它不大于 ``lower`` 堆顶就放入下半堆,否则放入上半堆;随后通过跨堆移动堆顶恢复大小平衡。
奇数个元素时中位数是 ``lower.top()``,偶数个元素时是两个堆顶的平均值。
正确性说明
----------
两个堆的顺序关系保证下半部分每个值都不大于上半部分每个值,大小平衡保证中间位置只可能落在
``lower.top`` 或两堆顶之间。加入元素后先按值放置,再至多移动一个元素纠正数量差,两个不变量始终成立,
所以查询得到排序序列的定义中位数。
C++ 实现
--------
.. code-block:: cpp
class MedianFinder {
std::priority_queue lower;
std::priority_queue, std::greater> upper;
public:
MedianFinder() = default;
void addNum(int num) {
if (lower.empty() || num <= lower.top()) lower.push(num);
else upper.push(num);
if (lower.size() > upper.size() + 1) {
upper.push(lower.top());
lower.pop();
} else if (upper.size() > lower.size()) {
lower.push(upper.top());
upper.pop();
}
}
double findMedian() {
if (lower.size() > upper.size()) return lower.top();
return (static_cast(lower.top()) + upper.top()) / 2.0;
}
};
代码分析
--------
每次加入元素最多执行常数次堆操作,时间复杂度为 ``O(log n)``;查询只读取堆顶,时间为 ``O(1)``。
两个堆合计保存全部数据,额外空间为 ``O(n)``;求偶数中位数时先在 ``long long`` 中相加再除以 ``2.0``,
保证平均值保留小数且不受整数除法影响。