题目描述
中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如,
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
-
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
-
double findMedian() - 返回目前所有元素的中位数。
样例
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
算法分析
添加一个元素时:
原则:大的元素往小根堆里面放,小的元素往大根堆里面放,保证A
和B
的值可以取到中位数,并且规定小根堆比大根堆最多多一个,设新来的元素是x
-
1、若
x >= B
或者大根堆为空,将其插入到上面 -
2、若
x < B
,将其插入到下面 -
3、维护大根堆和小根堆的数量关系:小根堆比大根堆最多多一个
-
一旦实现操作2时,则将大根堆中堆顶B元素
poll
出,并且插入到小根堆中 -
一旦
小根堆的数量 < 大根堆的数量 + 1
,则将小根堆元素poll
出,并且插入到大根堆中
-
-
4、获取中位数
-
若总体数量为奇数时,中位数为
A
-
若总体数量为偶数时,中位数为
(A + B)/2
-
C++ 代码
class MedianFinder {
PriorityQueue<Integer> up;
PriorityQueue<Integer> down;
/** initialize your data structure here. */
public MedianFinder() {
up = new PriorityQueue<Integer>();
down = new PriorityQueue<Integer>((x, y) -> y - x);
}
//由于输出的都是奇数个,默认小根堆的堆顶是中位数
public void addNum(int num)
{
//大于等于大顶堆顶则放上面
if(down.isEmpty() || num >= down.peek())
up.add(num);
//小于大堆顶则放下面
else {
down.add(num);
up.add(down.poll());
}
//维护小顶堆与大顶堆的大小关系
if(up.size() > down.size() + 1) {
down.add(up.poll());
}
}
public double findMedian()
{
if(up.size() == down.size() + 1)
return up.peek();
else return (double)(down.peek() + up.peek())/2;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
原则 那里应该是大元素入小根堆吧。
已修改,谢谢提醒hh