题解 | 数据流中的中位数

#include <functional>
#include <queue>
#include <vector>
class Solution {
private:
    priority_queue<int, vector<int>, greater<int>> minHeap;
    priority_queue<int, vector<int>, less<int>> maxHeap;
public:
    void Insert(int num) {
        if (maxHeap.size() == minHeap.size()) {
            minHeap.push(num);
            int x = minHeap.top();
            minHeap.pop();

            maxHeap.push(x);
        }
        if (maxHeap.size() > minHeap.size()) {
            maxHeap.push(num);
            int x = maxHeap.top();
            maxHeap.pop();
            
            minHeap.push(x);
        }
    }

    double GetMedian() { 
        double ans0 = 0.0, ans1 = 0.0;
        if (maxHeap.size() == minHeap.size()) {
            ans0 = maxHeap.top();
            ans1 = minHeap.top();
        }
        else {
            ans0 = maxHeap.top();
        }

        return ans1 == 0 ? ans0 : (ans0 + ans1) / 2.0;
    }

};

使用大根堆记录数据中较小的一半数据，使用小根堆记录数据中较大的一半数据，始终保持二者内部元素数量差 <= 1

• 若二者元素相同，则返回两个堆堆顶元素的均值
• 若大根堆数量比小根堆多1，则返回大根堆堆顶元素值

Day4