Find Median from Data Stream

Hard

The median is the middle value in an ordered list; for an even-sized list it is the average of the two middle values. Design a structure that supports a stream of integers. Implement MedianFinder with addNum(num) to add an integer, and findMedian() to return the median of all elements so far. Medians are reported to one decimal place (e.g. 2.0, 1.5).

Example 1

Input:  operations = ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"], values = [[],[1],[2],[],[3],[]]
Output: [null,null,null,1.5,null,2.0]

Constraints

• -10^5 <= num <= 10^5
• At most 5*10^4 calls to addNum and findMedian.
• findMedian is only called on a non-empty structure.