Find Median from Data Stream
给一个数据流(数组表示), 写一个API, 返回每个时刻的median. 因为是中间数, 所以我们可以把数据流看成两段数组的和, 考虑一下如果输入是一个已经排序好的数组, 那么中间的那个数就是答案. 所以我们只需要知道中间的两个数是哪两个就好, 这里用的是一个min heap和一个max heap, 来tracking中间的两个数. 需要注意如何保持两个heap的平衡, 即当放入min heap后, 需要poll最小的数放到max的里. 当然 如果输入的数组连续都是同样的数, 我们还要通过判断max和min的大小, 来重新平衡两个heap.
class MedianFinder {
private Queue<Integer> small = new PriorityQueue(1, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
};
});
private Queue<Integer> large = new PriorityQueue();
// Adds a number into the data structure.
public void addNum(int num) {
large.add(num); // add to min heap first
small.add(large.poll()); // poll the smallest to small
if (large.size() < small.size()) // if we pulled same number
large.add(small.poll());// poll back...
}
// Returns the median of current data stream
public double findMedian() {
return large.size() > small.size() // if the length is odd
? large.peek()
: (large.peek() + small.peek()) / 2.0;
}
}