The MedianFinder class finds the median of a data stream.
Implement addNum(int num) and findMedian() returning the median of current elements.
If the count is even, the median is the mean of the two middle values.
Example 1
Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, 2.0
-10^5 <= num <= 10^5At most 5*10^4 calls to addNum and findMedian.Two heaps: max-heap for lower half, min-heap for upper half. Balance sizes.
class MedianFinder {
private PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
private PriorityQueue<Integer> upper = new PriorityQueue<>(); // min-heap
public void addNum(int num) {
lower.offer(num); // always add to lower first
upper.offer(lower.poll()); // rebalance: push lower's max to upper
if (lower.size() < upper.size()) // lower should have >= upper size
lower.offer(upper.poll());
}
public double findMedian() {
if (lower.size() > upper.size()) return lower.peek();
return (lower.peek() + upper.peek()) / 2.0;
}
}Time: O(log n) addNum, O(1) findMedian · Space: O(n)