Calculating Quantiles
Problem statement
You have a population of N values. Number them 1 to N from lowest to highest, so position 1 holds the smallest value. For a whole number q, the k-th q-quantile is the value at position I_k = N * k / q. If I_k is not a whole number, round it up to the next whole number. There are q - 1 quantiles, one for each k from 1 to q - 1.
The population is given in compressed form. Each pairs[i] = [v, c] means the value v appears c times.
- The pairs can come in any order.
- The same value can be listed in more than one pair. Its counts add up.
Nis the sum of all the counts.
Return the q - 1 quantiles in order, from k = 1 to k = q - 1.
Function
calculateQuantiles(q: int, pairs: int[][]) → int[]Examples
Example 1
q = 2pairs = [[1,1],[2,3],[3,1]]return = [2]The pairs describe the values 1, 2, 2, 2, 3, so N = 5. With q = 2 there is one quantile: I_1 = ceil(5 * 1 / 2) = ceil(2.5) = 3. The 3rd value is 2.
Example 2
q = 3pairs = [[7,2],[6,2],[5,2]]return = [5,6]The pairs are not sorted. Sorted, the values are 5, 5, 6, 6, 7, 7, so N = 6.
I_1 = 6 * 1 / 3 = 2, and the 2nd value is5.I_2 = 6 * 2 / 3 = 4, and the 4th value is6.
Example 3
q = 2pairs = [[4,100000000],[5,100000000],[6,100000000]]return = [5]Each value appears 10^8 times, so N = 3 * 10^8. I_1 = 3 * 10^8 / 2 = 1.5 * 10^8. Positions 1 to 10^8 hold 4, and positions 10^8 + 1 to 2 * 10^8 hold 5, so the answer is 5.
Example 4
q = 5pairs = [[15,2],[3,2],[19,1],[5,3],[2,1],[18,2],[11,1],[8,1],[12,1],[6,1]]return = [3,5,11,15]Sorted, the 15 values are 2, 3, 3, 5, 5, 5, 6, 8, 11, 12, 15, 15, 18, 18, 19. With q = 5 the indices are 15 * k / 5 = 3, 6, 9, 12 for k = 1 to 4. Those positions hold 3, 5, 11, 15.
Constraints
2 <= q <= 10001 <= pairs.length <= 10^4pairs[i].length == 2-10^9 <= pairs[i][0] <= 10^91 <= pairs[i][1] <= 10^8