剑指 Offer 41 数据流中的中位数

标签: 剑指 Offer 发布于:2022-02-26 17:22:09 编辑于:2022-02-26 17:36:07 浏览量:389

概述

https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

https://leetcode.com/problems/find-median-from-data-stream/

最大堆最小堆法

维护一个最大堆一个最小堆,最小堆中所有元素不小于最大堆中所有元素,且保证两个堆元素个数相同或仅差一, 这样根据两个堆的堆顶就能计算出中位数。

实现的时候注意两点:

  1. 调用 minHeap.top() 时,有可能其为空,需要检查。
  2. 中位数可能为 double,而堆中元素为 int,注意要进行显式地类型转换。
class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    MedianFinder() {

    }
    
    void addNum(int num) {
        if (maxHeap.size() > minHeap.size()) {
            // add to minHeap
            if (num >= maxHeap.top()) {
                minHeap.push(num);
            } else {
                minHeap.push(maxHeap.top());
                maxHeap.pop();
                maxHeap.push(num);
            }
        } else {
            // add to maxHeap
            if (minHeap.empty() || num <= minHeap.top()) {
                maxHeap.push(num);
            } else {
                maxHeap.push(minHeap.top());
                minHeap.pop();
                minHeap.push(num);
            }
        }
    }
    
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (double(maxHeap.top()) + minHeap.top()) / 2;
        } else {
            return maxHeap.top();
        }
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/