394. Rarest First
A survey stores each respondent's answer as an integer code in the array nums. The organiser wants a report that lists the rarest answers first. Rearrange nums so that codes that occur fewer times in the array come earlier. When two different codes occur the same number of times, the code with the larger value comes first. All copies of one code must stay next to each other in the result.
Return the rearranged array. It contains exactly the same elements as nums.
Example 1
- Input:
- nums = [4,4,9,1,1,1,9,6]
- Output:
- [6,9,9,4,4,1,1,1]
- Explanation:
Counts are 6:1, 4:2, 9:2, 1:3. Code 6 comes first, then 9 before 4 (equal counts, larger value first), then the three 1s.
Example 2
- Input:
- nums = [2,-1,2,-1]
- Output:
- [2,2,-1,-1]
- Explanation:
Both codes appear twice, so the larger value 2 comes before -1, keeping each code's copies together.
Constraints
1 ≤ nums.length ≤ 105
-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)