Median After Each Number
Numbers arrive one at a time. The array nums lists them in the order they arrive.
After each new number arrives, find the median of all the numbers seen so far. Return an array of these medians. The value at position i is the median of nums[0] to nums[i].
The median of a group of numbers:
- Sort the group.
- If the group has an odd count, the median is the middle value.
- If the group has an even count, the median is the average of the two middle values. This can be a value like
3.5.
Hint
Sorting the whole group again after every number is slow. Keep the smaller half of the numbers in a max-heap and the larger half in a min-heap. Keep the two heaps the same size, or let one of them have one extra number. The median then comes from the top of the heaps. Each new number costs O(log n).
Note
Your answer is accepted if every value is within 10^-6 of the expected value.
Examples
Example 1
- Input:
- [6,2,9,4]
- Output:
- [6,4,6,5]
[6] gives 6. [2, 6] gives (2 + 6) / 2 = 4. [2, 6, 9] gives 6. [2, 4, 6, 9] gives (4 + 6) / 2 = 5.
Example 2
- Input:
- [-3,8,1]
- Output:
- [-3,2.5,1]
[-3] gives -3. [-3, 8] gives (-3 + 8) / 2 = 2.5. [-3, 1, 8] gives the middle value 1.
Example 3
- Input:
- [7,7,7]
- Output:
- [7,7,7]
When every number is the same, every median is that number.
Constraints
1 <= nums.length <= 40-1000 <= nums[i] <= 1000- Every
nums[i]is an integer.
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.