LeetCode 1636. Sort Array by Increasing Frequency

原题链接在这里：https://leetcode.com/problems/sort-array-by-increasing-frequency/

题目：

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Return the sorted array.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

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

Constraints:

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

题解：

HashMap to record num and its frequency.

Use bucket sort to add num into it corresponding frequency bucket.

Go through buckets and add value one by one.

Time Complexity: O(nlogk). n = nums.length. k is average size of bucket list item.

Space: O(n).

AC Java:

class Solution {
    public int[] frequencySort(int[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        
        int n = nums.length;
        int [] res = new int[n];
        HashMap hm = new HashMap<>();
        for(int num : nums){
            hm.put(num, hm.getOrDefault(num, 0) + 1);
        }
        
        ArrayList[] buckets = new ArrayList[n + 1];
        for(Map.Entry entry : hm.entrySet()){
            int freq = entry.getValue();
            if(buckets[freq] == null){
                buckets[freq] = new ArrayList();
            }
            
            for(int i = 0; i < freq; i++){
                buckets[freq].add(entry.getKey());
            }
        }
        
        int count = 0;
        for(int i = 0; i <= n; i++){
            if(buckets[i] != null){
                Collections.sort(buckets[i], (a, b) -> b - a);
                for(int num : buckets[i]){
                    res[count++] = num;
                }
            }
        }
        
        return res;
    }
}

类似, , .