1039. Value to Rank
A timing system records the finishing scores of a race in nums. Before printing the results the organisers want a lookup table from each score to its rank. The smallest distinct score gets rank 1, the next smallest distinct score gets rank 2, and so on. Equal scores share the same rank, and ranks never skip a number.
Return a map whose keys are the distinct values of nums and whose values are their 1-based ranks. The order of keys in the returned map does not matter.
Aim for O(n log n) time, dominated by sorting the distinct values.
Example 1
- Input:
- nums = [40,10,40,25]
- Output:
- {"10":1,"25":2,"40":3}
- Explanation:
The distinct values in increasing order are 10, 25, 40, so they receive ranks 1, 2 and 3.
Example 2
- Input:
- nums = [5]
- Output:
- {"5":1}
- Explanation:
A single value is the smallest and therefore has rank 1.
Example 3
- Input:
- nums = [-3,0,-3,8,0]
- Output:
- {"-3":1,"0":2,"8":3}
- Explanation:
Removing duplicates leaves -3, 0 and 8, which are ranked 1, 2 and 3.
Constraints
1 ≤ nums.length ≤ 105.
-231 ≤ nums[i] ≤ 231 - 1.
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)