Easy

题目描述

给你一个整数数组 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

解题思路

解题思路

这道题要求我们根据数字出现的频率进行排序，频率相同时按照数值降序排列。

核心思路：

  1. 首先统计每个数字的出现频率
  2. 使用自定义排序规则对数组进行排序

排序规则：

  • 优先按照频率升序排列（频率小的在前）
  • 频率相同时，按照数值降序排列（数值大的在前）

具体步骤：

  1. 使用哈希表统计每个数字的频率
  2. 对原数组使用自定义比较器进行排序
  3. 比较器逻辑：
    • 如果两个数的频率不同，频率小的排在前面
    • 如果两个数的频率相同，数值大的排在前面

这种方法简洁高效，时间复杂度主要由排序决定，空间复杂度取决于哈希表的大小。由于题目限制数值范围在[-100,100]，所以空间复杂度是常数级别的。

代码实现

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        sort(nums.begin(), nums.end(), [&](int a, int b) {
            if (freq[a] != freq[b]) {
                return freq[a] < freq[b];
            }
            return a > b;
        });
        
        return nums;
    }
};

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        from collections import Counter
        
        freq = Counter(nums)
        
        nums.sort(key=lambda x: (freq[x], -x))
        
        return nums

public class Solution {
    public int[] FrequencySort(int[] nums) {
        var freq = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
        
        Array.Sort(nums, (a, b) => {
            if (freq[a] != freq[b]) {
                return freq[a].CompareTo(freq[b]);
            }
            return b.CompareTo(a);
        });
        
        return nums;
    }
}

var frequencySort = function(nums) {
    const freq = new Map();
    for (let num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    
    nums.sort((a, b) => {
        if (freq.get(a) !== freq.get(b)) {
            return freq.get(a) - freq.get(b);
        }
        return b - a;
    });
    
    return nums;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要由排序操作决定，其中 n 是数组长度
空间复杂度O(k)哈希表存储频率信息，k 是不同数字的个数，最坏情况下 k = n

相关题目