查找数据里的中位数
程序员文章站
2022-06-17 19:54:54
...
使用两个堆,算法思路如下图所示。
class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue<double> maxPQ;
priority_queue<double, vector<double>, greater<double> > minPQ;
MedianFinder() {
}
void addNum(int num) {
if (maxPQ.empty()) {
maxPQ.push(num);
return;
}
if (maxPQ.size() == minPQ.size()) {
if (num < maxPQ.top())
maxPQ.push(num);
else
minPQ.push(num);
}
else if (maxPQ.size() == minPQ.size() + 1) {
if (num < maxPQ.top()) {
minPQ.push(maxPQ.top());
maxPQ.pop();
maxPQ.push(num);
}
else
minPQ.push(num);
}
else if (maxPQ.size() + 1 == minPQ.size()) {
if (num < minPQ.top())
maxPQ.push(num);
else {
maxPQ.push(minPQ.top());
minPQ.pop();
minPQ.push(num);
}
}
}
double findMedian() {
if (maxPQ.size() == minPQ.size())
return (maxPQ.top() + minPQ.top()) / 2;
else if (maxPQ.size() > minPQ.size())
return maxPQ.top();
else
return minPQ.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
上一篇: 有效的括号
推荐阅读
-
在ASP.NET 2.0中操作数据之二十八:GridView里的Button
-
在ASP.NET 2.0中操作数据之三十九:在DataList的编辑界面里添加验证控件
-
在ASP.NET 2.0中操作数据之四十五:DataList和Repeater里的自定义Button
-
python 实现查找文件并输出满足某一条件的数据项方法
-
电脑里数据突然没有了怎么办?恢复丢失数据的方法
-
解决PHP里大量数据循环时内存耗尽的方法
-
Sql Server里删除数据表中重复记录的例子
-
PHP使用递归按层级查找数据的方法
-
sql server 2012 数据库所有表里查找某字符串的方法
-
猎豹浏览器怎么查找缓存的音乐或者数据?