Find Median from Data Stream
给一个数据流(数组表示), 写一个API, 返回每个时刻的median. 因为是中间数, 所以我们可以把数据流看成两段数组的和, 考虑一下如果输入是一个已经排序好的数组, 那么中间的那个数就是答案. 所以我们只需要知道中间的两个数是哪两个就好, 这里用的是一个min heap和一个max heap, 来tracking中间的两个数. 需要注意如何保持两个heap的平衡, 即当放入min heap后, 需要poll最小的数放到max的里. 当然 如果输入的数组连续都是同样的数, 我们还要通过判断max和min的大小, 来重新平衡两个heap.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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; } } |