LC 1636. 按照频率将数组升序排序

题目描述

这是 LeetCode 上的 1636. 按照频率将数组升序排序 ，难度为 简单。

给你一个整数数组 nums，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。

请你返回排序后的数组。

示例 1：

输入：nums = [1,1,2,2,2,3]

输出：[3,1,1,2,2,2]

解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。

示例 2：

输入：nums = [2,3,1,3,2]

输出：[1,3,3,2,2]

解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。

示例 3：

输入：nums = [-1,1,-6,4,5,-6,1,4,1]

输出：[5,-1,4,4,-6,-6,1,1,1]

提示：

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

---

哈希表 + 排序 + 模拟

根据题意，先使用哈希表进行词频统计，再以二元组 $(x, cnt)$ 的形式转存到数组 list 中（其中 $x$ 为对应的 $nums$ 中的数值，$cnt$ 为数值 $x$ 在 nums 中的出现次数），再根据题目给定对 list 进行排序，最后再构造出答案。

Java 代码：

class Solution {
    public int[] frequencySort(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        List<int[]> list = new ArrayList<>();
        for (int key : map.keySet()) list.add(new int[]{key, map.get(key)});
        Collections.sort(list, (a, b)->{
            return a[1] != b[1] ? a[1] - b[1] : b[0] - a[0];
        });
        int[] ans = new int[n];
        int idx = 0;
        for (int[] info : list) {
            int a = info[0], b = info[1];
            while (b-- > 0) ans[idx++] = a;
        }
        return ans;
    }
}

TypeScript 代码：

function frequencySort(nums: number[]): number[] {
    const map = new Map<number, number>()
    for (const x of nums) {
        if (!map.has(x)) map.set(x, 0)
        map.set(x, map.get(x) + 1)
    }
    nums.sort((a,b)=>{
        return map.get(a) != map.get(b) ? map.get(a) - map.get(b) : b - a
    })
    return nums
};

• 时间复杂度：使用哈希表进行统计复杂度为 $O(n)$；根据规则进行排序复杂度为 $O(n\log{n})$；构造答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1636 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。