295. 数据流的中位数
3 min
题目
解法：对顶堆
思路
使用两个堆（最大堆和最小堆）分别存储较小和较大的一半数，通过堆顶元素快速获取中位数。
该方法通过两个堆维护中位数：最大堆 lo 存储较小的一半数，最小堆 hi 存储较大的一半数。插入时先将元素放入 lo，再将 lo 的堆顶移到 hi 确保 lo 的所有元素 <= hi 的所有元素；最后如果 lo 的大小小于 hi，则将 hi 的堆顶移回 lo，保证 lo 的大小 >= hi 且两者大小差不超过 1。这样中位数要么是 lo 的堆顶（奇数个元素），要么是两堆堆顶的平均值（偶数个元素）。
- Step 1: 将新元素插入最大堆 lo
- Step 2: 将 lo 的堆顶移到最小堆 hi
- Step 3: 如果 lo 的大小小于 hi，将 hi 的堆顶移回 lo
- Step 4: 查询时，若 lo 大小大于 hi 则返回 lo 堆顶，否则返回两堆堆顶的平均值
复杂度
- 时间复杂度: 每次操作，堆插入/删除耗时 ，查询中位数耗时 。
- 空间复杂度: ，两个堆共同存储所有元素。
代码
class MedianFinder {
public:
priority_queue<int> lo; // max heap
priority_queue<int, vector<int>, greater<int>> hi; // min heap
MedianFinder() {
}
void addNum(int num) {
lo.push(num); // Add to max heap
hi.push(lo.top()); // balancing step
lo.pop();
if (lo.size() < hi.size()) { // maintain size property
lo.push(hi.top());
hi.pop();
}
}
double findMedian() {
return lo.size() > hi.size()
? (double)lo.top()
: (lo.top() + hi.top()) * 0.5;
}
class MedianFinder {
public:
priority_queue<int> lo; // max heap
priority_queue<int, vector<int>, greater<int>> hi; // min heap
MedianFinder() {
}
void addNum(int num) {
lo.push(num); // Add to max heap
hi.push(lo.top()); // balancing step
lo.pop();
if (lo.size() < hi.size()) { // maintain size property
lo.push(hi.top());
hi.pop();
}
}
double findMedian() {
return lo.size() > hi.size()
? (double)lo.top()
: (lo.top() + hi.top()) * 0.5;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/