Heaps Two heaps
420. Find Median from Data Stream
Numbers arrive one at a time, and at any moment you may be asked for the median of all the numbers so far.
Write a class MedianFinder with two methods:
addNum(num)adds the integernumto the numbers seen so far.findMedian()returns the median of all the numbers added so far, as a floating-point number.
The median is the middle number once the numbers are sorted. When there is an even count of numbers, there
are two middle numbers, and the median is their average. So the median of [5, 1, 3] is 3, and the median
of [5, 1, 3, 8] is (3 + 5) / 2 = 4.
Your class is tested by replaying a list of calls on a new MedianFinder. ops[i] names the i-th call,
"addNum" or "findMedian". The addNum calls take their numbers from nums in order, so the first one adds
nums[0], the second adds nums[1], and so on. The answer is the list of every value that findMedian
returns, in order. The output writes each median with one digit after the point, as in 4.0 or 2.5.
In C# and Go the methods are AddNum and FindMedian, and in Rust add_num and find_median. Go creates the
finder with Constructor(), and Rust with MedianFinder::new(). The names in ops are the same in every
language.
Example 1
Input: ops = ["addNum",
"findMedian",
"addNum",
"findMedian",
"addNum",
"findMedian",
"addNum",
"findMedian"]
nums = [6, 10, 2, 7]
[6.0,8.0,6.0,6.5]Explanation: The numbers so far are [6], then [6, 10], then [2, 6, 10] and [2, 6, 7, 10] once sorted. The last
median is the average of 6 and 7.
Example 2
Input: ops = ["addNum",
"addNum",
"findMedian",
"addNum",
"findMedian",
"addNum",
"findMedian"]
nums = [-5, 3, -5, 0]
[-1.0,-5.0,-2.5]Explanation: [-5, 3] has median -1. After the second -5 the middle of [-5, -5, 3] is -5. With 0 added, the middle
pair of [-5, -5, 0, 3] is -5 and 0.
Example 3
Input: ops = ["addNum",
"addNum",
"findMedian",
"addNum",
"findMedian"]
nums = [1000000000, -1000000000, 1000000000]
[0.0,1000000000.0]Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ ops.length ≤ 105- Each
ops[i]is"addNum"or"findMedian". nums.lengthequals the number of"addNum"calls inops.-109 ≤ nums[i] ≤ 109findMedianis only called after at least oneaddNum.
Clarifying questions
What you would ask an interviewer before writing any code.