题解 | #牛体重的中位数计算#

#include <functional>
#include <queue>
#include <vector>

class KeepTopK {
  private:
    // 第 k 大，用小顶堆维护，将前 k 大放在此处。
    priority_queue<int, vector<int>, greater<>> topK =
                priority_queue<int, vector<int>, greater<>>();
    // 剩余元素，用大顶堆维护
    priority_queue<int> buffer = priority_queue<int>();
    int k;

    // 将 topK 中的元素下放一个到 buffer 中
    void pushDown() {
        buffer.push(topK.top());
        topK.pop();
    }

    // 将 buffer 中的元素提出一个到 topK 中
    void pushUp() {
        topK.push(buffer.top());
        buffer.pop();
    }


  public:
    void add(int x) {
        topK.push(x);
        update(k);
    }

    void update(int k) {
        this->k = k;
        while (topK.size() > k) pushDown();
        while (topK.size() < k && buffer.size() > 0) pushUp();

    }

    double get(int k) {
        update(k);
        return topK.top();
    }


};

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weights int整型vector
     * @return double浮点型vector
     */
    vector<double> calculateMedians(vector<int>& weights) {
        // write code here
        for (int i = 1 ; i <= weights.size(); ++i) { // i 是第几个
            top.add(weights[i - 1]); // 注意 -1
            if (i % 2 > 0) { // 奇数
                double tmp = top.get((i + 1) / 2);
                ans.push_back(tmp);
            } else {
                double tmp = (top.get(i / 2) + top.get(i / 2 + 1)) / 2;
                ans.push_back(tmp);
            }
        }
        return ans;
    }
    vector<double> ans = vector<double>();
    KeepTopK top = KeepTopK();



};