Find Median from Data Stream

The median of a sorted list is its middle value, or the average of the two middle values when the length is even.

Design a class MedianFinder:

• MedianFinder() starts with no numbers.
• add_num(num) adds an integer from the stream.
• find_median() returns the median of all numbers added so far (as a float; answers within 1e-5 are accepted).

Example 1

Input:
["MedianFinder", "add_num", "add_num",
 "find_median", "add_num", "find_median"]
[[], [1], [2], [], [3], []]
Output: [None, None, None, 1.5, None, 2.0]

[1, 2] → 1.5; [1, 2, 3] → 2.0

Example 2

Input:
["MedianFinder", "add_num", "find_median",
 "add_num", "find_median", "add_num",
 "find_median"]
[[], [-4], [], [10], [], [-1], []]
Output: [None, None, -4.0, None, 3.0, None, -1.0]

Constraints

• -10^5 <= num <= 10^5
• find_median is only called after at least one add_num
• Up to 5 * 10^4 calls in total