中位数——题解

中位数

思路简介

使用两个堆，大根堆维护较小的值，小根堆维护较大的值

即小根堆的堆顶是较大的数中最小的，大根堆的堆顶是较小的数中最大的

将大于大根堆堆顶的数（比所有大根堆中的元素都大）的数放入小根堆，小于等于大根堆堆顶的数（比所有小根堆中的元素都小）的数放入大根堆

那么就保证了所有大根堆中的元素都小于小根堆中的元素

于是我们发现对于大根堆的堆顶元素，有【小根堆的元素个数】个元素比该元素大，【大根堆的元素个数-1】个元素比该元素小；

同理，对于小跟堆的堆顶元素，有【大根堆的元素个数】个元素比该元素小，【小根堆的元素个数-1】个元素比该元素大；

那么维护【大根堆的元素个数】和【小根堆的元素个数】差值不大于1之后，元素个数较多的堆的堆顶元素即为当前中位数；（如果元素个数相同，那么就是两个堆堆顶元素的平均数，本题不会出现这种情况）

根据这两个堆的定义，维护方式也很简单，把元素个数多的堆的堆顶元素取出，放入元素个数少的堆即可

代码

#include<bits/stdc++.h>
using namespace std;
int read(){//读入优化
	int x=0;bool f=0;char c=getchar();
	while (c<‘0‘||c>‘9‘){if (c==‘-‘)f=1;c=getchar();}
	while (c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
priority_queue<int,vector<int> > q1;//大根堆
priority_queue<int,vector<int>,greater<int> > q2;//小根堆
int main(){
	int n=read();q1.push(read());
	cout<<q1.top()<<endl; 
	for (int i=2;i<=n;i++){
		int input=read();//等同于cin>>input
		if (input>q1.top()) q2.push(input);
			else q1.push(input);
		while (abs(q1.size()-q2.size())>1)
			if (q1.size()>q2.size()){q2.push(q1.top());q1.pop();}
				else{q1.push(q2.top());q2.pop();}
		if (i%2) cout<<(q1.size()>q2.size()?q1.top():q2.top())<<endl;
	}
	return 0;
}

我们可以直接套用STL模板库中的vector来做，用到我们的upper_bound和lower_bound函数来解决这道题

#include<bits/stdc++.h>
using namespace std;
int main(){
	vector<int>vct;
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		vct.insert(upper_bound(vct.begin(),vct.end(),x),x);
		if(i%2==1){
			cout<<vct[(i-1)/2]<<endl;
		}
	}
	return 0;
}

中位数——题解

原文：https://www.cnblogs.com/wozuishuaiwozuiniu6/p/13178887.html