知识点

对顶堆

思路

动态维护中位数。可以搞两个堆,一个是较小的一半数(大顶堆),一个是较大的一半数(小顶堆),较小元素的堆至多比较大元素的堆多一个元素。这样每次求中位数,要么是小数堆的堆顶,要么是小数堆和大数堆的堆顶的平均数,单次时间复杂度为O(1)

然后考虑如何维护这两个堆。每次我们加入一个新的元素,先加入大顶堆,然后假如大顶堆的堆顶大于小顶堆的堆顶元素(就是刚才加入那个数比较大),调换两个堆的堆顶。之后假如小数的堆个数比大数的堆多两个元素以上了,需要调一个元素过去。单次维护的时间复杂度是O(logn)

一共进行n次,总的时间复杂度为O(nlogn)

AC code(C++)

#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return double浮点型vector
     */
    vector<double> findMedianPrice(vector<int>& prices) {
        // 两个堆
        vector<double> res;
        priority_queue<int, vector<int>, greater<>> r;
        priority_queue<int> l;
        int n = prices.size();
        for (int i = 0; i < n; i ++) {
            l.push(prices[i]);
            if (r.size() and l.top() > r.top()) {
                auto t1 = l.top();
                l.pop();
                auto t2 = r.top();
                r.pop();
                l.push(t2), r.push(t1);
            }
            if (l.size() - r.size() == 2) {
                r.push(l.top());
                l.pop();
            }

            if (i & 1) {
                res.push_back(0.5 * (l.top() + r.top()));
            }
            else res.push_back(1.0 * l.top());
        }
        return res;
    }
};