数据流的中心(两个堆,堆插入复杂度最低)

数据流中的中位数

http://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1

/*
堆排序插入O(logn) 得到中位数为O(1);
插入排序插入,折、、半查找为O(logN),移动为O(n) 得到中位数 为O(1)
如果插入数字小于大根堆(存放的是数组小的值,存放数组左边)的最大值(第一个值) 加入
否则加入小根堆(存放数组右边)
*/
class Solution {
public:
    priority_queue<int> left;
    priority_queue<int,vector<int>, greater<int>> right;
    void Insert(int num)
    {
        left.push(num);
        right.push(left.top());
        left.pop();
        if(right.size() > left.size()){ //右边的堆比左边高 平衡
            left.push(right.top());// 且每次只高一个高度
            right.pop();
        }

    }

    double GetMedian()
    { 
        return (left.size() > right.size())? left.top(): (left.top()+right.top())/2.0;
    }

};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 11:15
点赞 评论 收藏
分享
lllllkin:感觉可以精简到一页简历,有些排版感觉不是必须的。 时间线越早的,你自己越熟悉的放前面。描述可以更精简些,一些问题解决感觉可以不用写具体技术栈,卖个关子,等面试官问。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务