题目描述
对于插入和查询两种操作,动态维护序列的中位数。
样例
输入
["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
算法1
(优先队列) $O(nlogn)$
将序列一分为二,用大根堆维护做左半段序列的最大值,小根堆维护右半段序列的最小值。
如果大小根堆数目的和为偶数,则中位数为最大值加最小值的和/2.0,否则就是中位数。这里我们维持大根堆的数目 >= 小根堆
C++ 代码
class MedianFinder {
public:
priority_queue<int> l;
priority_queue<int,vector<int>,greater<int> > r;
MedianFinder() {
}
void addNum(int num) {
if(l.size()==r.size()){
if(r.size()==0) l.push(num);
else if(r.top()<=num) { // 单纯放进右边序列会导致右边序列元素多一个,所以我们取右边的top放到左边。
int u=r.top();r.pop();
l.push(u);
r.push(num);
}
else {
l.push(num); // 破坏个数相等关系,保证左边序列多一个。
}
}else{
if(l.top()<=num){
r.push(num);
}else{
int u=l.top();l.pop();
r.push(u);
l.push(num);
}
}
}
double findMedian() {
if(l.size()==r.size()) return (l.top()+r.top())/2.0;
return l.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/