Loading problem…
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement the MedianFinder class: - MedianFinder() initializes the MedianFinder object. - void addNum(int num) adds the integer num from the data stream to the data structure. - double findMedian() returns the median of all elements so far.
Example 1
Input: operations = ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"], arguments = [[],[1],[2],[],[3],[]]
Output: [null,null,null,1.5,null,2.0]
Explanation: After adding 1 and 2, the list is [1,2] and the median is (1 + 2) / 2 = 1.5. After adding 3, the list is [1,2,3] and the middle value is 2.
Example 2
Input: operations = ["MedianFinder","addNum","findMedian"], arguments = [[],[1],[]]
Output: [null,null,1.0]
Explanation: The list is just [1], so the median is 1.
Example 3
Input: operations = ["MedianFinder","addNum","addNum","findMedian"], arguments = [[],[1],[1],[]]
Output: [null,null,null,1.0]
Explanation: The list is [1,1], and the average of the two middle values is (1 + 1) / 2 = 1.
Split the stream at the median: everything below goes into a **max-heap** `low`, everything above into a **min-heap** `high`. Keep `|low| - |high| ∈ {0, 1}`. - `|low| == |high|` → median = `(low.top + high.top) / 2`. - `|low| == |high| + 1` → median = `low.top`. Python has only min-heaps, so negate values for `low`.
Run checks all cases above. Submit evaluates all test cases.