Find Median from Data Stream
HardHeap
Design a MedianFinder that receives integers one at a time and can report the median of everything seen so far at any moment.
The median of a sorted list of c values is the middle value when c is odd, and the average of the two middle values when c is even. For example, the median of [1, 5, 9] is 5 and the median of [1, 5, 9, 12] is (5 + 9) / 2 = 7.0.
Implement the class:
MedianFinder()creates an empty structure.addNum(num)adds the integernumto the stream.findMedian()returns the median of all numbers added so far as a float. It is only called after at least one number has been added.
Calls can be interleaved in any order, so both operations need to be fast; re-sorting the data on every call is too slow for the largest inputs.
The examples list the calls in order; the output shows each call's return value, with None for the constructor and addNum.
Example 1
- Input:
- MedianFinder(); addNum(6); findMedian(); addNum(10); findMedian(); addNum(2); findMedian()
- Output:
- [None, None, 6.0, None, 8.0, None, 6.0]
- Explanation
- With just
[6]the median is 6. With[6, 10]the count is even, so the median is(6 + 10) / 2 = 8.0. With[2, 6, 10]the middle value is 6 again.
Example 2
- Input:
- MedianFinder(); addNum(-4); addNum(7); addNum(-1); addNum(3); findMedian()
- Output:
- [None, None, None, None, None, 1.0]
- Explanation
- Sorted, the four values are
-4, -1, 3, 7. The two middle values are -1 and 3, and their average is 1.0.
Example 3
- Input:
- MedianFinder(); addNum(1); addNum(4); findMedian()
- Output:
- [None, None, None, 2.5]
- Explanation
- The median of an even count can be a fraction:
(1 + 4) / 2 = 2.5.
Constraints
-10^5 <= num <= 10^5findMedianis only called after at least oneaddNum- At most
5 * 10^4total calls toaddNumandfindMedian