首页 > 其他 > 详细

54. 数据流中的中位数

时间:2020-02-17 15:53:56      阅读:72      评论:0      收藏:0      [点我收藏+]

 

技术分享图片

 

 

思路:AcWing 54. 数据流中的中位数

           将数组分成两半,一个大顶堆和一个小顶堆,大顶堆维护小于中位数的所有元素,小顶堆维护大于中位数的所有元素,两个堆的元素数量差不能超过2,超过2就互相匀一匀。

技术分享图片

 

 

 

代码:

 

class Solution {
        priority_queue<int> maxHeap;//大顶堆维护小于中位数的所有元素
        priority_queue<int, vector<int>, greater<int>> minHeap;//小顶堆维护大于中位数的所有元素。数字越大,优先级越低
public:
    void insert(int num){
        maxHeap.push(num);//每次直接把当前数插入到下一个堆
        /*两个堆的元素数量差不能超过2,超过2就互相匀一匀*/
        if(maxHeap.size() > minHeap.size() + 1)
        {
            int t = maxHeap.top();
            maxHeap.pop();
            minHeap.push(t);
        }
        /*如果大顶堆最大值 大于 小顶堆最小值,则交换*/
        while(minHeap.size() && maxHeap.top() > minHeap.top())//保证大顶堆有元素,同时大顶堆最大值大于小顶堆最小值
        {
            int t1 = maxHeap.top();
            int t2 = minHeap.top();
            maxHeap.pop(); maxHeap.push(t2);
            minHeap.pop(); minHeap.push(t1);
        }
    }

    double getMedian(){
        int n1 = minHeap.size();
        int n2 = maxHeap.size();
        if(n1 == n2) return (minHeap.top() + maxHeap.top()) / 2.0;
        else return maxHeap.top();
    }
};

 

54. 数据流中的中位数

原文:https://www.cnblogs.com/make-big-money/p/12321473.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!