题解 | #售价的中位数#

考察的知识点：优先队列、对顶堆

题目分析：

因为序列可能是无序的，每加入一个数就需要对所有数进行排序。如果我们将排好序的序列一分为二，发现中位数只与左边序列的最大值和右边序列的最小值有关。可以通过使用对顶堆找到这个最大值和最小值，即使用大顶堆保存左边较小的序列，可以直接获得这些序列中的最大值；使用小顶堆保存右边较大的序列，可以直接获得这些序列中的最小值。

构造这两个堆需要注意两点：

1. 为了让更大的数放在上面的堆上，如果新加入的价格大于中位数，则将该价格放入上面的小顶堆中；反之放入下面的大顶堆中。
2. 为了让大顶堆中容纳数的范围是从1~N / 2 （注意向0取整），小顶堆中容纳数的范围是(N + 1) / 2 ~ N，当各个堆中的元素数量小于理应存放的个数时，将另一个堆中的数转移到这个堆中即可。

最后，因为中位数是第(N + 1) / 2个数，所以当元素个数总共为奇数个时，返回小顶堆的堆顶；否则返回两个堆中堆顶的和除以2。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return double浮点型vector
     */
    vector<double> findMedianPrice(vector<int>& prices) {
        // write code here
        priority_queue<int, vector<int>, greater<int>> gheap;
        priority_queue<int, vector<int>, less<int>> lheap;
        vector<double> res;
        int mid = 0;
        int k = 0;
        for (auto &price: prices) {
            if (price > mid) gheap.push(price);
            else lheap.push(price);
            k++;
            if  (gheap.size() < (k + 1) / 2) {
                gheap.push(lheap.top());
                lheap.pop();
            }
            if (lheap.size() < k / 2) {
                lheap.push(gheap.top());
                gheap.pop();
            }
            if (k % 2) res.push_back(gheap.top());
            else {
                res.push_back(((double)gheap.top() + lheap.top()) / 2);
            }
            mid = gheap.top();
        }
        return res;
    }
};