Find Median from Data Stream
Examples
Example 1:
Input: ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
Output: [null, null, null, 1.5, null, 2.0]
Explanation:
Example 1:
Input: ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
Output: [null, null, null, 1.5, null, 2.0]
Explanation:
The median is the middle value in a sorted list of integers. For lists of even length, there is no middle value, so the median is the mean of the two middle values.
For example:
arr = [1,2,3], the median is 2.arr = [1,2], the median is (1 + 2) / 2 = 1.5Implement 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.MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 medianFinder.addNum(3); // arr = [1, 2, 3] medianFinder.findMedian(); // return 2.0
-100,000 <= num <= 100,000findMedian will only be called after adding at least one integer to the data structure.