题解 | #数据流中的中位数#

数据流中的中位数

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

public:
    //使用两个堆来存储数据,
    priority_queue<int> maxheap;   //大根堆,默认降序排列,队列头的元素最大
    priority_queue<int, vector<int>, greater<int>> minheap; //队头元素最小
    void Insert(int num) {
        maxheap.push(num);
        if(minheap.size() && maxheap.top() > minheap.top()){
            int a = maxheap.top(); maxheap.pop();
            int b = minheap.top(); minheap.pop();
            maxheap.push(b), minheap.push(a);
        }
        if(maxheap.size()> minheap.size() + 1){
            minheap.push(maxheap.top());
            maxheap.pop();
        }
    }

    double GetMedian() { 
        if((maxheap.si***heap.size()) & 1) return maxheap.top();
        return (maxheap.top() + minheap.top()) / 2.0;
    }    

};
全部评论

相关推荐

12-04 19:53
已编辑
湖南文理学院 产品经理
牛客224543458号:他想找牛马,愿意疯狂加班的,因为要证明自己
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务