197. Find Median from Data Stream

Hard · Heap

Design a data structure that supports adding numbers and finding the median efficiently.

Implement the `MedianFinder` class: - `addNum(num)`: Add an integer to the data structure. - `findMedian()`: Return the median of all elements added so far.

The median is the middle value in a sorted list. If the list has an even number of elements, the median is the average of the two middle elements.

Examples

Example 1
Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: 1.5, 2.5
Explanation: After adding 1 and 2, the sorted list is [1, 2], median is (1+2)/2 = 1.5. After adding 3, the sorted list is [1, 2, 3], median is 2.
Example 2
Input: addNum(5), findMedian(), addNum(15), findMedian(), addNum(1), findMedian(), addNum(3), findMedian()
Output: 5, 10, 5, 4
Explanation: After [5]: median is 5. After [5, 15]: median is (5+15)/2 = 10. After [5, 15, 1]: median is 5. After [5, 15, 1, 3]: median is (3+5)/2 = 4.

Constraints