Running Median

问题：给奇数个数( int范围内)，依次输出1~ i (1<=i<=n)内的中位数，i 为奇数。
思路：经典题目？，据说什么主席树（可持久化线段树），红黑树，平衡树 ……都可以解？，不会。
这里用对顶堆解法：开一个大根堆，一个小根堆，依次将数插入两个堆，同时维护大根堆里放的是较小的一半数，小根堆里放的是较大的一半数，当到奇数位置时大根堆堆顶就是中位数。

#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--){
int t,n,x,num=0;
scanf("%d%d",&t,&n);
priority_queue<int> Q1;
//大根堆，存较小的那一半数
priority_queue<int,vector<int>,greater<int> > Q2;	//小根堆，存较大的那一半数
for(int i=1;i<=n;i++){
if(i==1) printf("%d %dn",t,(n+1)/2);
scanf("%d",&x);
if(i&1) Q1.push(x);
else Q2.push(x);
if(i>=2){
int a= Q1.top(),b = Q2.top();
if(a>b){
//保证Q1中的数小于或等于Q2中的数
Q1.pop(),Q2.pop();
Q1.push(b),Q2.push(a);
}
}
if(i&1) printf("%d ",Q1.top());
if(i%20==0) printf("n");
}
printf("n");
}
return 0;
}

最后

以上就是自信唇彩为你收集整理的Running Median (中位数)Running Median的全部内容，希望文章能够帮你解决Running Median (中位数)Running Median所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。