求stream-data的中位数
题意ref
解法:
对顶堆,主要维护一个 大顶堆 和 小顶堆,同时维护下面的性质
1. 小顶堆(top) 的数 都大于 大顶堆(bottom) 的数
2. 小顶堆的个数a,大顶堆的个数b,保持 a==b or a == b+1;
C++ 代码
class MedianFinder {
public:
MedianFinder() {
}
void addNum(int num) {
int tsz = htop_.size(), bsz = hbottom_.size();
if(htop_.empty()) {
htop_.push(num);
}
else if(bsz == tsz) {
htop_.push(num);
// 先 push 再 调整
if(htop_.top() < hbottom_.top()) {
htop_.push(hbottom_.top());
hbottom_.push(htop_.top());
hbottom_.pop();
htop_.pop();
}
} else {
hbottom_.push(num);
if(hbottom_.top() > htop_.top()) {
hbottom_.push(htop_.top());
htop_.push(hbottom_.top());
hbottom_.pop();
htop_.pop();
}
}
}
double findMedian() {
int tsz = htop_.size(), bsz = hbottom_.size();
int tot = tsz + bsz;
double res = 0;
if(tot&1)res = htop_.top();
else {
double x = htop_.top(), y = hbottom_.top();
res = (x+y)/2.0;
}
cerr << res << endl;
return res;
}
private:
priority_queue<int, vector<int>, greater<int>> htop_;
priority_queue<int, vector<int>, less<int>> hbottom_;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/