希望大佬帮忙解答

剑指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();
    }
}

};
#笔试题目#
全部评论

相关推荐

头像
05-12 09:14
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务