0295. Find Median from Data Stream¶
题目信息¶
- 题号:
0295
- 难度:
Hard
- 主题:
数据流、对象设计、中位数、跨调用状态
- 原题:
- 重点:
新数据持续加入、奇偶数量对应不同中位数定义、查询必须覆盖此前全部元素
题目重述¶
实现 MedianFinder 类,用于持续接收整数并查询当前数据集合的中位数:
MedianFinder()创建一个尚未加入数据的对象;addNum(num)把整数num加入当前数据流;findMedian()返回截至当前已经加入的全部整数的中位数。
把已有元素按非递减顺序排列后,元素数量为奇数时,中位数是正中间的元素;数量为偶数时,中位数是中间两个元素的算术平均值,因此返回类型为浮点数。num 位于 [-10^5, 10^5],题目保证调用 findMedian 前至少加入过一个元素。addNum 与 findMedian 的总调用次数不超过 5 * 10^4,对象必须在不同调用之间保留此前全部数据的逻辑状态。
自建示例¶
数据量从偶数变为奇数:
操作:addNum(5), addNum(1), findMedian(), addNum(9), findMedian()
输出:3.0, 5.0
解释:前两项排序后为 [1,5],中位数是 (1+5)/2=3;加入 9 后为 [1,5,9],中位数是 5。
继续加入负数:
操作: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++ 实现¶
class MedianFinder {
std::priority_queue<int> lower;
std::priority_queue<int, std::vector<int>, std::greater<int>> 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<long long>(lower.top()) + upper.top()) / 2.0;
}
};
代码分析¶
每次加入元素最多执行常数次堆操作,时间复杂度为 O(log n);查询只读取堆顶,时间为 O(1)。
两个堆合计保存全部数据,额外空间为 O(n);求偶数中位数时先在 long long 中相加再除以 2.0,
保证平均值保留小数且不受整数除法影响。