1731. Running Percentile
A support team tracks how long each customer waits, and the readings of nums arrive one by one. The manager follows a service-level percentile p: after the i-th reading arrives (counting from 1), she wants the reading whose rank is ceil(p * i / 100) when the first i readings are sorted in ascending order, using 1-based ranks. For example, p = 50 asks for the lower median and p = 100 asks for the maximum so far.
Return an int[] of length n holding that value after every arrival. Equal readings count separately, so the answer is unique. A solution using two heaps runs in O(n log n) time and O(n) space.
Example 1
- Input:
- nums = [5,2,8,1], p = 50
- Output:
- [5,2,5,2]
- Explanation:
With p = 50 the ranks are 1, 1, 2, 2, giving 5, 2, 5 and 2 after sorting each prefix.
Example 2
- Input:
- nums = [4,9,1,7,3], p = 90
- Output:
- [4,9,9,9,9]
- Explanation:
With p = 90 the ranks are 1, 2, 3, 4, 5, so the answers are 4, 9, 9, 9 and 9.
Constraints
1 ≤ n ≤ 1000
1 ≤ p ≤ 100
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)