知识点
对顶堆
思路
动态维护中位数。可以搞两个堆,一个是较小的一半数(大顶堆),一个是较大的一半数(小顶堆),较小元素的堆至多比较大元素的堆多一个元素。这样每次求中位数,要么是小数堆的堆顶,要么是小数堆和大数堆的堆顶的平均数,单次时间复杂度为。
然后考虑如何维护这两个堆。每次我们加入一个新的元素,先加入大顶堆,然后假如大顶堆的堆顶大于小顶堆的堆顶元素(就是刚才加入那个数比较大),调换两个堆的堆顶。之后假如小数的堆个数比大数的堆多两个元素以上了,需要调一个元素过去。单次维护的时间复杂度是。
一共进行n次,总的时间复杂度为。
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; } };