希望大佬帮忙解答
剑指offer第63题:如何得到一个数据流的中位数。用vs2015可以运行成功,但是在牛客网上一直不能通过,希望大佬帮忙解答
class Solution {
public:priority_queue<int, vector<int>, less<int> > q1; //通过操作,按照元素从大到小的顺序出队
priority_queue<int, vector<int>, greater<int> > q2;//通过操作,按照元素从小到大的顺序出队
void Insert(int num)
{
if (q1.empty())
{
q1.push(num);
return;
}
if (q1.top() >= num)
{
q1.push(num);
}
else
{
if(q2.empty())
{
q2.push(num);
return;
}
if(q2.top()>num)
q1.push(num);
else{
q2.push(num);
}
}
modifyTwoHeapSize();
}
double GetMedian()
{
int maxSize = q1.size();
int minSize = q2.size();
if (minSize + maxSize == 0)
return 0;
int maxTop = q1.top();
int minTop = q2.top();
if (((maxTop + minTop) & 1) == 0)
return (maxTop + minTop) / 2;
else if (maxSize>minSize)
return q1.top();
else
{
return q2.top();
}
}
void modifyTwoHeapSize()
{
if (q1.size() == q2.size() + 2)
{
q2.push(q1.top());
q1.pop();
}
if (q2.size() == q1.size() + 2)
{
q1.push(q2.top());
q2.pop();
}
}
};
#笔试题目#