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

数据流中的中位数

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

#include <queue>
#include <vector>
class Solution {
public:
    priority_queue<int>min_q;//存放较小数据的大根堆,堆顶即为最大数
    priority_queue<int,vector<int>,greater<int>>max_q; //存放较大数据的小根堆,堆顶即为最小数
    void Insert(int num) {
        //约定当为奇数时,从大根堆取中位数,固先将数放入大根堆
        min_q.push(num);
        max_q.push(min_q.top());//将大根堆最大数放入小根堆,保持小根堆的数始终大于大根堆
        min_q.pop();
        //当小根堆的数比大根堆多时,从小根堆取最小数放入大根堆,保持大根堆大小始终大于小根堆
        if(max_q.size()>min_q.size()){
            min_q.push(max_q.top());
            max_q.pop();
        }
    }
    double GetMedian() { 
        if(min_q.size()>max_q.size()){
            return (double)min_q.top();
        }
        return (double)(min_q.top()+max_q.top())/2;
    }

};

全部评论

相关推荐

昨天 15:12
门头沟学院 Java
别人在上班,我就在工位上看看视频啥的,这正常吗?
程序员小白条:实习就是摸鱼,只是公司指标,把你进来了,可能那时候客户很多,但等你进来的时候,已经是淡季了,根本没多少需求,或者说根本不适合实习生去完成,因此你就每天干坐着就行,可能1,2个月都没需求
实习生的蛐蛐区
点赞 评论 收藏
分享
宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:20
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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