普通网友 2021-11-11 14:08 采纳率: 42.9%
浏览 6
已结题

数据流中的中位数 数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数

img

  • 写回答

1条回答 默认 最新

  • 从善若水 5G/6G通信领域优质创作者 2021-11-11 14:18
    关注
    
    class Solution {
        priority_queue<int, vector<int>, less<int> > p;
        priority_queue<int, vector<int>, greater<int> > q;
        
    public:
        void Insert(int num){
            if(p.empty() || num <= p.top()) p.push(num);
            else q.push(num);
            if(p.size() == q.size() + 2) q.push(p.top()), p.pop();
            if(p.size() + 1 == q.size()) p.push(q.top()), q.pop();
        }
        double GetMedian(){ 
            return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();
        }
    };
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

问题事件

  • 系统已结题 11月18日
  • 已采纳回答 11月11日
  • 创建了问题 11月11日
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部