剑指 Offer 41. 数据流中的中位数
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
例如,
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1:
输入:
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]
示例 2:
输入:
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]
限制:
最多会对 addNum、findMedian 进行 50000 次调用。
这道题目的思考,从题目我们大概需要将插入,获取结果控制在O(LogN)这个范围,那么说到LogN,说明插入的是树形结构,而优先级队列的插入正好是logN,但是在优先级队列寻找中位数的时间是O(N)级别的,那么就不满足题意,一个思路就是用两个优先级队列,一个dqmax为大堆,一个dqmin为小堆,两个堆相互调整保证数据量相差最多为1.就可以O(1)取中位数。
那么如何保证两个优先级队列的数量最多差一且保证dqmax的最大值比dqmin的最小值小呢?
1.由于我们每次只插入一个数,假设两个堆数量相等,实际上插入任意一边都可以,但是若出现插入0,插入7,我们希望插入0的时候往大堆插入,插入7往小堆插入,但是这有没有用一种方式表示呢?
观察下面这张图,当我们插入0,7如果都往其中一个堆插入(如小堆,都可以的),那么此时0的情况会导致小堆中出现比大堆小的数,那么我们可以将堆顶的弹出,给到大堆。
那么实际上不管插入0还是7,这样子做了之后,都能保证小堆当中的数都比大堆的大!!!
则实际上大堆的数量+1,小堆的数量不变。
2.那么按照上面逻辑,我们大堆就有可能比小堆多一个。因为相等的时候我们实际上往大堆填入一个。
此时我们为了保证两个堆的数量差不超过1,选择往小堆插入,若是插入7,问题解决,若是插入-1,则再次出现小堆中的数比大堆大!! 那么怎么处理,我们上面那种做法一开始插入小堆再匀给大堆,最终小堆数量没变,大堆数量加一;那么我们这里可以选择给大堆添加节点。
按照上面说法,小堆的数量+1,大堆数量不变,即 m == n的情况。就可以反复如上过程。
最终结果,若m == n,则取两个堆的头/2,若m > n,说明返回大堆头就是中位数了。
class MedianFinder {
public:
priority_queue<int> dqmax;//大堆
priority_queue<int,vector<int>,greater<int> > dqmin;//小堆
int m= 0 ;//记录大堆的数量
int n = 0;//记录小堆的数量
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
//大堆永远多一个
if(m == n)
{
dqmin.push(num);
m ++;
dqmax.push(dqmin.top());
dqmin.pop();
}
else
{
dqmax.push(num);
n ++;
dqmin.push(dqmax.top());
dqmax.pop();
}
}
double findMedian() {
if(m == n)
{
return (dqmax.top() + dqmin.top()) /2.0;
}
return dqmax.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
end