My code:
public class MedianFinder {
PriorityQueue<Integer> big = new PriorityQueue<Integer>();
PriorityQueue<Integer> small = new PriorityQueue<Integer>();
// Adds a number into the data structure.
public void addNum(int num) {
big.offer(num);
small.offer(-1 * big.poll());
if (small.size() > big.size()) {
big.offer(-1 * small.poll());
}
}
// Returns the median of current data stream
public double findMedian() {
if (big.size() > small.size()) {
return big.peek() * 1.0;
}
else {
return (big.peek() - small.peek()) / 2.0;
}
}
};
// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();
this solution is so cool.
自己没能写出来，看了答案，理解了，再写，还是错。然后才终于理解了原答案中一些我觉得完全必要的步骤，其实完全是有必要的。
reference:
https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1
他其实就是维护两个堆，一个是 Min-heap, 一个是 max-heap
然后 min-heap 放整个数据流右半部分的数据，即，较大的数据那部分。
max-heap 放整个数据流左半部分的数据，即，较小的数据那部分。
然后， top of max-heap and top of min-heap 正好是中间的值。
如果个数是奇数，那就是 top of min-heap 是 median
如果个数是偶数，那就是 (top of min-heap + top of max-heap) / 2
然后他用了两个技巧来实现这么两个堆。
1.每次先往最小堆加入元素。
然后 Poll 出来，这时候poll 出来的一定是右半部分最小的数值。
？？ 但他也一定是左半部分最大的数值。把它押进左半部分。 ？？
如果此时左半部分个数大于了右半部分的，那么再把左半部分的最小大值，弹出来给右半部分
- 正如上面打问号的部分，这个说法是错的。
如果刚进来的值就是最小的，那么他就会被 big 弹出来，然后插入small, small 再把他里面最大的值弹出来给big
所以这里其实有一个reheap 的过程。我一开始忽略掉了，所以有错。
为了实现 max-heap 的效果，small 都是插入负值，这样，优先级就会颠倒。也就是 map-heap 了。
Anyway, Good luck, Richardo! -- 09/15/2016
