#include <stdio.h>
#include <queue>
class MedianFinder {
public:
MedianFinder() {
}
void addNum(int num) {
if (big_queue.empty()){
big_queue.push(num);
return;
}
if (big_queue.size() == small_queue.size()){
if (num < big_queue.top()){
big_queue.push(num);
}
else{
small_queue.push(num);
}
}
else if(big_queue.size() > small_queue.size()){
if (num > big_queue.top()){
small_queue.push(num);
}
else{
small_queue.push(big_queue.top());
big_queue.pop();
big_queue.push(num);
}
}
else if(big_queue.size() < small_queue.size()){
if (num < small_queue.top()){
big_queue.push(num);
}
else{
big_queue.push(small_queue.top());
small_queue.pop();
small_queue.push(num);
}
}
}
double findMedian(){
if (big_queue.size() == small_queue.size()){
return (big_queue.top() + small_queue.top()) / 2;
}
else if (big_queue.size() > small_queue.size()){
return big_queue.top();
}
return small_queue.top();
}
private:
std::priority_queue<double> big_queue;
std::priority_queue<double, std::vector<double>,
std::greater<double>> small_queue;
};
int main(){
MedianFinder M;
int test[] = {6, 10, 1, 7, 99, 4, 33};
for (int i = 0; i < 7; i++){
M.addNum(test[i]);
printf("%lf\n", M.findMedian());
}
return 0;
}
如何将c++ 优先队列求中位数代码修改为模板类?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- i_actor 2020-12-03 15:17关注
#include<iostream> #include<queue> template <typename T> class MedianFinder { private: std::priority_queue<T> big_queue; std::priority_queue<T, std::vector<T>, std::greater<T>> small_queue; public: MedianFinder(){} template <typename U> void addNum(U& num) { if (big_queue.empty()) { big_queue.push(num); return; } if (big_queue.size() == small_queue.size()) { if (num < big_queue.top()) big_queue.push(num); else small_queue.push(num); } else if (big_queue.size() > small_queue.size()) { if (num > big_queue.top()) small_queue.push(num); else { small_queue.push(big_queue.top()); big_queue.pop(); big_queue.push(num); } } else if (big_queue.size() < small_queue.size()) { if (num < small_queue.top()) big_queue.push(num); else { big_queue.push(small_queue.top()); small_queue.pop(); small_queue.push(num); } } } T findMedian() { if (big_queue.size() == small_queue.size()) return (big_queue.top() + small_queue.top()) / 2; else if (big_queue.size() > small_queue.size()) return big_queue.top(); else return small_queue.top(); } }; int main() { MedianFinder<double> M; int test[] = { 6, 10, 1, 7, 99, 4, 33 }; for (auto i = 0; i < 7; i++) { M.addNum(test[i]); printf("%lf\n", M.findMedian()); } return 0; }
不知道对不对,我也是正在学习。
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 如何在scanpy上做差异基因和通路富集?
- ¥20 关于#硬件工程#的问题,请各位专家解答!
- ¥15 关于#matlab#的问题:期望的系统闭环传递函数为G(s)=wn^2/s^2+2¢wn+wn^2阻尼系数¢=0.707,使系统具有较小的超调量
- ¥15 FLUENT如何实现在堆积颗粒的上表面加载高斯热源
- ¥30 截图中的mathematics程序转换成matlab
- ¥15 动力学代码报错,维度不匹配
- ¥15 Power query添加列问题
- ¥50 Kubernetes&Fission&Eleasticsearch
- ¥15 報錯:Person is not mapped,如何解決?
- ¥15 c++头文件不能识别CDialog