考到了琐馆，完全沒反應(yīng)過來。這里是用兩個heap來保存stream里的數(shù)恒序；max heap保存小的那一半瘦麸，min heap保存大的那一半數(shù)。這樣的話歧胁，當(dāng)兩個heap里的數(shù)個數(shù)相同的時候滋饲，（maxPQ.peek + minPQ.peek）/2 就是median; 而且始終保持maxPQ的個數(shù)等于或比minPQ 的個數(shù)大于一，這樣的話maxPQ.peek()就是兩者個數(shù)不相等時的median
class MedianFinder {
PriorityQueue<Integer> minPQ;
PriorityQueue<Integer> maxPQ;
/** initialize your data structure here. */
public MedianFinder() {
//keep the larger half of the integer stream
minPQ = new PriorityQueue<>();
//keep the smaller half of the integer stream
maxPQ = new PriorityQueue<>(1000, Collections.reverseOrder());
}
public void addNum(int num) {
maxPQ.add(num);
minPQ.add(maxPQ.poll());
if (maxPQ.size() < minPQ.size()){
maxPQ.offer(minPQ.poll());
}
}
public double findMedian() {
if (maxPQ.size() == minPQ.size()){
return (maxPQ.peek() + minPQ.peek()) / 2.0;
} else {
return maxPQ.peek();
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
