Find Median From Data Stream
Implement MedianFinder with addNum(num) and findMedian(). Return the middle value of all inserted numbers, or the average of the two middle values when the count is even.
Example 1
arg 1 = ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
arg 2 = [[],[8],[2],[],[3],[]][null,null,null,5,null,3]Explanation
8 and 2 average to 5; after adding 3 the sorted middle is 3.
Example 2
arg 1 = ["MedianFinder","addNum","findMedian","addNum","findMedian"]
arg 2 = [[],[-5],[],[-1],[]][null,null,-5,null,-3]Explanation
One negative is its own median; -5 and -1 average to -3.
Example 3
arg 1 = ["MedianFinder","addNum","findMedian","addNum","findMedian","addNum","findMedian"]
arg 2 = [[],[4],[],[4],[],[4],[]][null,null,4,null,4,null,4]Explanation
Repeated 4 values remain distinct observations with median 4 at odd and even counts.
Constraints
- At most 50000 operations
- Values are -100000..100000
- findMedian is called only after insertion
Class contract
MedianFinderArguments: json, jsonSolutionRuns on your device
Loading draft…
Run: 3 examples; Submit: 35 cases, on your device.
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"][[],[8],[2],[],[3],[]]