LeetCode: Sort Array by Increasing Frequency

Description

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.

Solution: HashMap + Sort

Use a Map to store the counts of each elements, and then sort depends on the frequencies and values.
The key point is define the customized sort function.

CPP

class Solution {
public:
    static bool cmp(pair<int, int>& l, pair<int, int>& r) {
        if(l.second != r.second) return l.second < r.second;
        return l.first > r.first;
    }

    vector<int> frequencySort(vector<int>& nums) {
        vector<pair<int, int>> pairs;
        map<int, int> counts;
        
        for(int i=0; i < nums.size(); i++) { 
            auto it = counts.find(nums[i]);
            if(it == counts.end()) counts[nums[i]] = 1;
            else it->second++;
        }
        for(auto it = counts.begin(); it != counts.end(); it++) 
            pairs.push_back(make_pair(it->first, it->second));
        sort(pairs.begin(), pairs.end(), cmp);

        vector<int> res;
        for(int i=0; i<pairs.size(); i++) {
            for(int k=0; k<pairs[i].second; k++) {
                res.push_back(pairs[i].first);
            }
        }
        return res;
    }
};

A simpler implementation for C11:

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (auto n : nums) {
            cnt[n]++;
        }
        sort(nums.begin(), nums.end(), [&cnt](int a, int b) {
            return (cnt[a] == cnt[b]) ? a > b : cnt[a] < cnt[b];
        });
        return nums;
    }
};

Java

class Solution {
    public int[] frequencySort(int[] nums) {
        Integer[] arr = new Integer[nums.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (Integer) nums[i];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        Arrays.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                if(map.get(a).equals(map.get(b))) {
                    return b - a;
                }
                return map.get(a) - map.get(b);
            }
        });
       return Arrays.stream(arr).mapToInt(Integer::valueOf).toArray();
    }
}

Python

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        num_dict = {}
        for k in nums:
            if k not in num_dict:
                num_dict[k]=1
            else:
                num_dict[k]=num_dict[k]+1
        
        num_dict = sorted(num_dict.items(), key = lambda x:(x[1],-x[0]))
        res = []
        for key,value in num_dict:
            res += [key]*value
        return res

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← LeetCode: Reverse Words in a Str... LeetCode: Divisor Game →