问题
题解
将窗口的元素分成两堆，使得一堆所有元素都>=中位数，另一堆所有元素都<=中位数。用两个优先队列维护这两个堆，maxHeap和minHeap规定maxHeap.size()-minHeap.size()==1或0，这样当两堆元素总个数为奇数时，maxHeap.peek()就是所需要的中位数，若为偶数，则中位数=maxHeap.peek()/2.0+minHeap.peek()/2.0；关键在于维持maxHeap.size()-minHeap.size()==1或0这个关系，每次移动两个堆内元素都需要整理两个堆的元素，使其满足上述数量关系。添加元素时，判断与两个堆堆顶的大小关系，再决定放入到哪个堆中。在heap中放入数据为O(logn)
class MedianFinder {
PriorityQueue
<Integer> maxHeap
;
PriorityQueue
<Integer> minHeap
;
public MedianFinder() {
maxHeap
= new PriorityQueue<Integer>((Collections
.reverseOrder()));
minHeap
= new PriorityQueue<Integer>();
}
public void addNum(int num
) {
if(maxHeap
.isEmpty() || maxHeap
.peek() >= num
){
maxHeap
.add(num
);
}else{
minHeap
.add(num
);
}
balanceHeap(maxHeap
, minHeap
);
}
public double findMedian() {
if(maxHeap
.size() > minHeap
.size()){
return maxHeap
.peek();
}else{
return maxHeap
.peek() / 2.0 + minHeap
.peek() / 2.0;
}
}
public void balanceHeap(PriorityQueue
<Integer> maxHeap
, PriorityQueue
<Integer> minHeap
){
if(maxHeap
.size() < minHeap
.size()){
maxHeap
.add(minHeap
.poll());
}else if(maxHeap
.size() > minHeap
.size() + 1){
minHeap
.add(maxHeap
.poll());
}
}
}
