Description
The median is the middle value in an ordered integer list. Implement the MedianFinder class that supports addNum(int num) to add an integer and findMedian() to return the median of all elements so far.
Examples
Input:
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]Output:
[null, null, null, 1.5, null, 2.0]Explanation:
After adding 1 and 2, median is 1.5. After adding 3, median is 2.0.
Input:
[["MedianFinder", "addNum", "addNum", "addNum", "findMedian", "addNum", "addNum", "findMedian"], [[], [10], [5], [15], [], [20], [8], []]]Output:
[null, null, null, null, 10.0, null, null, 10.0]Explanation:
After adding 10, 5, 15, the sorted order is [5, 10, 15], so median is 10.0. After adding 20 and 8, the sorted order is [5, 8, 10, 15, 20], so median remains 10.0 (middle element of 5 elements).
Input:
[["MedianFinder", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"], [[], [-1], [], [-3], [], [0], [], [2], []]]Output:
[null, null, -1.0, null, -2.0, null, -1.0, null, -0.5]Explanation:
Starting with -1, median is -1.0. Adding -3 gives [-3, -1], median is (-3 + -1)/2 = -2.0. Adding 0 gives [-3, -1, 0], median is -1.0. Adding 2 gives [-3, -1, 0, 2], median is (-1 + 0)/2 = -0.5.
Constraints
- •
-10⁵ ≤ num ≤ 10⁵ - •
There will be at least one element before calling findMedian. - •
At most 5 × 10⁴ calls will be made to addNum and findMedian.