题目描述
分析：大根堆小根堆法
现在假设数组有序，如果我们把数组的前半部分放入一个大根堆，数组的后半部分放入一个小根堆，那么中位数就只能是大根堆的堆顶元素和小根堆的堆顶元素，或者二者堆顶元素的平均值
我们在插入的时候只有遵循某种规则，就能达到这种效果
插入的时候两个堆的元素数量不同，则将新元素插入数量少的堆
若元素数量相同，则随便插入一个堆
若大根堆的堆顶元素大于小根堆的堆顶元素，则交换其堆顶元素
插入完成后，根据元素的数量来确定中位数的值
时间复杂度：插入一个数O（N*log N）,获取中位数O（1）
class Solution
{
public: priority_queue<int,vector<int>,less<int> > q1; //大根堆
priority_queue<int,vector<int>,greater<int> > q2; //小根堆 //插入数
void Insert(int um)
{
int x=um; //插入规则
if(q1.size()==q2.size())
{
q2.push(x);
}
else if(q2.size()>q1.size())
{
q1.push(x);
}
else if(q1.size()>q2.size())
{
q2.push(x);
} //根据大根堆小根堆堆顶元素的关系判断是否交换堆顶元素，
//保证堆中的数据是正确的
//(即大根堆保存有序数组前半部分的元素，小根堆保存有序数组后半部分的元素)
if(q1.size()!=0&&q2.size()!=0)
{
if(q1.top()>q2.top())
{
int a=q1.top();
int b=q2.top();
q1.pop();
q2.pop();
q1.push(b);
q2.push(a);
}
}
}
double GetMedian()
{
double x; //根据元素的数量奇偶和元素的分布来求中位数
if(q1.size()==q2.size())
{
x=(q1.top()*1.0+q2.top()*1.0)/2.0;
}
else if(q2.size()>q1.size())
{
x=q2.top()*1.0;
}
else if(q1.size()>q2.size())
{
x=q1.top()*1.0;
}
return x;
}
};