题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

题解1：使用排序 题解2：使用大小根堆

代码：

/*
	描述
	如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
	那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
	那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，
	使用GetMedian()方法获取当前读取数据的中位数。
*/
/*
	题解1：使用数组排序
	题解2：使用大小根堆----------推荐用法
	大根堆    priority_queue<int> maxheap;保存中位数左边的小值
	小根堆    priority_queue<int,vector<int>,greater<int> > minheap; 保存中位数右边的大值
	小根堆    priority_queue<类型,<存储方式>,<比较函数>空格 >  注意：空格必须有，否则可能引起歧义
*/
#include<iostream>
using namespace std;
#include<queue>
#include<vector>
/*
	题解1：数组排序--暴力法
*/
vector<int> v;
void Insert(int num) {
	v.push_back(num);
}

double GetMedian() {
	sort(v.begin(), v.end());//排序
	int size = v.size();
	if (size & 1)//奇数
		return static_cast<double>(v[size >> 1]);
	else
		return static_cast<double>(v[(size >> 1)] + v[(size - 1) >> 1]) / 2;
}
/*
	题解2：大小根堆----------推荐用法
*/
priority_queue<int> maxheap;
priority_queue<int, vector<int>, greater<int> > minheap;
void Insert(int num) {
	if (maxheap.si***heap.size()) {
		//为了保证maxheap中的元素都小于minheap中的元素，先将元素存放在minheap
		minheap.push(num);
		//然后将minheap中的最小值取出并存放在maxheap中
		maxheap.push(minheap.top());
		minheap.pop();
	}
	else {//为偶数时候，将元素排序后的元素放在小根堆中
		//为了保证minheap中的元素都大于maxheap中的元素，先将元素存放在maxheap
		maxheap.push(num);
		//然后将maxheap中的最大值取出并存放在minheap中
		minheap.push(maxheap.top());
		maxheap.pop();
	}
}
double GetMedian() {
	if (maxheap.si***heap.size())//容器中个数相等，说明为偶数
		return static_cast<double>(maxheap.top() + minheap.top()) / 2;
	else
		return static_cast<double>(maxheap.top());
}
int main() {

	system("pause");
	return 0;
}