Find Median from Data Stream
The median of a list of numbers is its middle value once sorted. With an even count there is no single middle, so the median is the average of the two middle values: the median of [1, 3, 4, 8] is (3 + 4) / 2 = 3.5.
Implement the class MedianFinder, which receives numbers one at a time:
new MedianFinder()creates an empty structure.addNum(num)adds the integernum.findMedian()returns the median of all numbers added so far. Answers within10^-5of the true median are accepted.
findMedian is only called after at least one addNum. Both methods will be called many times, interleaved, so re-sorting on every call is too slow. JavaScript has no built-in heap: write your own.
Constraints
-10^5 <= num <= 10^5- At most
5 * 10^4calls in total toaddNumandfindMedian.
Examples
Example 1
Input: ["MedianFinder","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian"]
[[],[6],[],[2],[],[9],[],[1],[]]
Output: [null,null,6,null,4,null,6,null,4]After 6 the median is 6. After 2 the two middle values are 2 and 6, so 4. After 9 the sorted values are 2, 6, 9: the median is 6. After 1 they are 1, 2, 6, 9: (2 + 6) / 2 = 4.
Example 2
Input: ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
Output: [null,null,null,1.5,null,2]With 1 and 2 the median is their average, 1.5. Adding 3 makes the middle value 2.
Example 3
Input: ["MedianFinder","addNum","findMedian"]
[[],[-7],[]]
Output: [null,null,-7]One value is its own median.
Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.
JavaScript you'll use: Heaps and priority queues Classes for data structures
// JavaScript has no built-in heap: write a small one (push, pop, peek, size) above this class.
class MedianFinder {
constructor() {
}
/**
* Adds a number to the data structure.
* @param {number} num
* @return {void}
*/
addNum(num) {
}
/**
* @return {number} the median of all numbers added so far
*/
findMedian() {
}
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.