LeetCode 1636. Sort the array in ascending order by frequency

1636. Sort the array in ascending order by frequency

Give you an array of integers nums , Please arrange the array according to the frequency of each value Ascending Sort . If there are multiple values with the same frequency , Please put them according to the value itself Descending Sort .

Please return the sorted array .

Example 1：

 Input ：nums = [1,1,2,2,2,3]
 Output ：[3,1,1,2,2,2]
 explain ：'3'  The frequency is  1,'1'  The frequency is  2,'2'  The frequency is  3 .

Example 2：

 Input ：nums = [2,3,1,3,2]
 Output ：[1,3,3,2,2]
 explain ：'2'  and  '3'  The frequencies are  2 , So they are sorted in descending order according to the value itself .

Example 3：

 Input ：nums = [-1,1,-6,4,5,-6,1,4,1]
 Output ：[5,-1,4,4,-6,-6,1,1,1]

Tips ：

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

Two 、 Method 1

Hash + Priority queue

class Solution {
    
    public int[] frequencySort(int[] nums) {
    
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
    
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2)
         -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]
        );
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
    
            queue.add(new int[]{
    entry.getValue(), entry.getKey()});
        }
        int[] res = new int[nums.length];
        int idx = 0;
        while (!queue.isEmpty()) {
    
            int[] pos = queue.poll();
            for (int i = 0; i< pos[0]; i++) {
    
                res[idx++] = pos[1];
            }
        }
        return res;
    }
}

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(n).