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

概述

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();
        }
    }
};

Links: sword-offer-41

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