A shopkeeper writes down the bill of each customer as the day goes on. At any time, she wants the median of all the bills so far.
The median is the middle value when the numbers are sorted. If the count is even, there is no single middle value. Then the median is the average of the two middle values.
- The median of
[10,40,70] is 40.
- The median of
[10,40] is (10 + 40) / 2 = 25.
Write a class MedianFinder with these methods:
MedianFinder(): make an empty finder.addNum(num): add the whole number num to the numbers seen so far.findMedian(): return the median of all numbers added so far, as a decimal number. An answer within 10^-5 of the true value is accepted.
Examples
Example 1:
Input
["MedianFinder", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
[[], [50], [], [10], [], [90], [], [30], []]
Output
[null, null, 50.0, null, 30.0, null, 50.0, null, 40.0]
Explanation
addNum(50) // numbers: 50
findMedian() // 50.0, the only number
addNum(10) // numbers: 10, 50
findMedian() // 30.0, the average of 10 and 50
addNum(90) // numbers: 10, 50, 90
findMedian() // 50.0, the middle one
addNum(30) // numbers: 10, 30, 50, 90
findMedian() // 40.0, the average of 30 and 50
Example 2:
Input
["MedianFinder", "addNum", "addNum", "addNum", "findMedian", "addNum", "addNum", "findMedian"]
[[], [-4], [-4], [6], [], [0], [2], []]
Output
[null, null, null, null, -4.0, null, null, 0.0]
Explanation
After adding -4, -4 and 6, the sorted numbers are -4, -4, 6. The middle one is -4.0.
After adding 0 and 2, the sorted numbers are -4, -4, 0, 2, 6. The middle one is 0.0.