【剑指Offer】T41 数据流中的中位数

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

思路:

  • 借助两个堆,大根堆 max 和小根堆 min
    • 大根堆存放中位数左边的数字
    • 小根堆存放中位数右边的数字
  • 需要满足:大根堆堆顶(最大) <= 小根堆堆顶(最小)
  • 存入的时候维护堆,取出的时候要么是两堆顶平均数要么是大根堆顶
class Solution {
    priority_queue<int, vector<int>, less<int> > max;
    priority_queue<int, vector<int>, greater<int> > min;
public:
    void Insert(int num){
        if(max.empty() || num <= max.top())
            max.push(num);
        else
            min.push(num);
        
        // 控制max.size()大于min.size()且不超过2
        // 原因是,max堆内是从 最小值 增长到 中位数,两堆堆相等时取平均值,相差1时取大堆顶
        if(max.size() - min.size() == 2){
            // max堆顶到min
            min.push(max.top());
            max.pop();
        }
        
        if(min.size() - max.size() == 1){
            // min堆顶到max
            max.push(min.top());
            min.pop();
        } 
    }

    double GetMedian(){ 
        // 两堆堆相等时取平均值,相差1时取大堆顶
        return max.size() == min.size() ? (max.top() + (min.top() - max.top())/2.0) : max.top();
    }
};

本文链接:https://ariser.cn/index.php/archives/390/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!