Medium

题目描述

给定一个字符串 s，根据字符出现的频率对其进行降序排序。一个字符出现的频率是它在字符串中出现的次数。

返回已排序的字符串。如果有多个答案，返回其中任何一个都可以。

示例 1：

输入: s = "tree"
输出: "eert"
解释: 'e' 出现两次，'r' 和 't' 都只出现一次。
因此 'e' 必须出现在 'r' 和 't' 之前。因此 "eetr" 也是一个有效的答案。

示例 2：

输入: s = "cccaaa"
输出: "aaaccc"
解释: 'c' 和 'a' 都出现了三次，所以 "cccaaa" 和 "aaaccc" 都是有效的答案。
注意 "cacaca" 是不正确的，因为相同的字母必须放在一起。

示例 3：

输入: s = "Aabb"
输出: "bbAa"
解释: "bbaA" 也是一个有效答案，但 "Aabb" 是不正确的。
注意 'A' 和 'a' 被认为是两个不同的字符。

提示：

  • 1 <= s.length <= 5 * 10^5
  • s 由大小写英文字母和数字组成

解题思路

这道题的核心思路是统计字符频率并按频率排序。有三种常见解法：

解法1：哈希表+排序（推荐）

  1. 使用哈希表统计每个字符的出现频率
  2. 将字符-频率对放入数组，按频率降序排序
  3. 根据排序后的结果构建答案字符串

解法2：桶排序

  1. 统计字符频率后，使用桶排序的思想
  2. 创建频率桶，每个桶存储具有相同频率的字符
  3. 从高频率桶向低频率桶遍历构建结果

解法3：优先队列 使用最大堆来维护字符按频率的排序，每次取出频率最高的字符。

第一种解法最直观且效率较好，适合大多数情况。桶排序在字符种类较少时有优势，但需要额外的桶空间。优先队列解法代码简洁但有额外的堆操作开销。

代码实现

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        vector<pair<char, int>> charFreq;
        for (auto& p : freq) {
            charFreq.push_back({p.first, p.second});
        }
        
        sort(charFreq.begin(), charFreq.end(), [](const pair<char, int>& a, const pair<char, int>& b) {
            return a.second > b.second;
        });
        
        string result;
        for (auto& p : charFreq) {
            result += string(p.second, p.first);
        }
        
        return result;
    }
};

class Solution:
    def frequencySort(self, s: str) -> str:
        from collections import Counter
        
        freq = Counter(s)
        sorted_chars = sorted(freq.items(), key=lambda x: x[1], reverse=True)
        
        result = []
        for char, count in sorted_chars:
            result.append(char * count)
        
        return ''.join(result)

public class Solution {
    public string FrequencySort(string s) {
        var freq = new Dictionary<char, int>();
        foreach (char c in s) {
            freq[c] = freq.GetValueOrDefault(c, 0) + 1;
        }
        
        var charFreq = freq.ToList();
        charFreq.Sort((a, b) => b.Value.CompareTo(a.Value));
        
        var result = new StringBuilder();
        foreach (var pair in charFreq) {
            result.Append(new string(pair.Key, pair.Value));
        }
        
        return result.ToString();
    }
}

var frequencySort = function(s) {
    const freq = {};
    for (const char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    
    const charFreq = Object.entries(freq);
    charFreq.sort((a, b) => b[1] - a[1]);
    
    let result = '';
    for (const [char, count] of charFreq) {
        result += char.repeat(count);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表+排序O(n + k log k)O(k)
桶排序O(n + k)O(n)
优先队列O(n + k log k)O(k)

其中 n 是字符串长度，k 是不同字符的数量（最多128个ASCII字符）。

相关题目