Median of a Number Stream
Problem statement
Integers arrive one at a time, in the order given by nums. At certain moments you are asked for the median of all the numbers that have arrived so far: checkpoints[j] means "after the first checkpoints[j] numbers have arrived".
The median of m numbers is found by sorting them:
- if
mis odd, it is the middle number; - if
mis even, it is the average of the two middle numbers, which can end in.5.
Return the median for each checkpoint, in order.
Function
mediansAt(nums: int[], checkpoints: int[]) → double[]Examples
Example 1
nums = [5,15,1,3,8]checkpoints = [1,2,3,4,5]return = [5.0,10.0,5.0,4.0,5.0]After each number: [5] has median 5. [5, 15] has two middle values, so the median is (5 + 15) / 2 = 10. Sorted, [1, 5, 15] has median 5, [1, 3, 5, 15] has median (3 + 5) / 2 = 4, and [1, 3, 5, 8, 15] has median 5.
Example 2
nums = [-2,-7,4,4]checkpoints = [2,4]return = [-4.5,1.0]After 2 numbers, sorted [-7, -2]: the median is (-7 + -2) / 2 = -4.5. After 4 numbers, sorted [-7, -2, 4, 4]: the median is (-2 + 4) / 2 = 1.
Example 3
nums = [100000,-100000]checkpoints = [2]return = [0.0]Only one checkpoint, after both numbers. The two middle values are the extremes, and their average is 0.
Constraints
1 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^51 <= checkpoints.length <= 500checkpointsis strictly increasing and every value is between1andnums.length.