31. Find Median from Data Stream
Implement a class that finds the median from a data stream. 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 as follows:
- MedianFinder() initializes the MedianFinder object.
- void addNum(int num) adds the integer num to the data structure.
- double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: [MedianFinder(), addNum(1), addNum(2), addNum(3), findMedian()]
Output: [null, null, null, null, 2]
Explanation:
MedianFinder(): initializes the object.
addNum(1): adds 1 to the data structure
addNum(2): adds 2 to the data structure
addNum(3): adds 3 to the data structure
findMedian(): returns 2 as the median of [1, 2, 3]
Example 2:
Input: [MedianFinder(), addNum(1), addNum(6), findMedian(), addNum(3), findMedian()]
Output: [null, null, null, 3.5, null, 3]
Explanation:
MedianFinder(): initializes the object.
addNum(1): adds 1 to the data structure
addNum(6): adds 6 to the data structure
findMedian(): returns 3.5 as the median of [1, 6] -> (1 + 6) / 2 = 3.5
addNum(3): adds 3 to the data structure
findMedian(): returns 3 as the median of [1, 3, 6].
Now Your Turn!
Pick the correct output for the given inputInput: [MedianFinder(), addNum(1), findMedian(), addNum(80), addNum(6), findMedian()]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= Number of instructions <= 104
- -104 <= num <= 104
- There will be at least 1 element in the data structure before any median call