451. 根据字符出现频率排序
题目描述
输入字符串 s。某个字符的频率是它在 s 中出现的次数。
重新排列 s 中的全部字符：频率高的字符排在前面，同一个字符的所有副本必须挨在一起。
返回排好的字符串。频率相同的不同字符谁先谁后都可以，任一合法结果均可。大写字母和小写字母视为不同字符。
示例 1
输入：s = "tree" 输出："eetr"
解释：'e' 出现 2 次排在最前，'t' 和 'r' 各 1 次，顺序任意。
示例 2
输入：s = "cccaaa" 输出："cccaaa"
解释：'c' 和 'a' 都是 3 次，各自连成一段即可。
示例 3
输入：s = "Aabb" 输出："bbAa"
解释：'b' 出现 2 次在前；'A' 与 'a' 是不同字符，各 1 次。
数据范围
1 <= s.length <= 5 * 10^5s由大小写英文字母和数字组成。
解题思路：计数 + 桶排序
先用哈希表统计每个字符出现几次。频率最多是 len(s)，所以不必真的排序：建 len(s)+1 个桶，把字符放进“它的次数”号桶。然后从大号桶往小号桶走，每个字符写出 c 次，就得到了按频率降序的结果。这是用计数代替比较排序（堆或 sort）的典型做法。
为什么正确
从高到低遍历桶时，已经写出的每个字符的频率都不小于还没写出的任何字符的频率。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
大小写字母是不同的字符（"Aabb" 中 A 和 a 各 1 次）。另外桶的下标是次数，最大可能等于 len(s)，数组要开 len(s)+1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def frequencySort(self, s: str) -> str:
cnt = collections.Counter(s)
buckets = [[] for _ in range(len(s) + 1)]
for ch, c in cnt.items():
buckets[c].append(ch)
res = []
for c in range(len(s), 0, -1):
for ch in buckets[c]:
res.append(ch * c)
return ''.join(res)class Solution {
public String frequencySort(String s) {
Map<Character, Integer> cnt = new HashMap<>();
for (char ch : s.toCharArray()) cnt.merge(ch, 1, Integer::sum);
List<List<Character>> buckets = new ArrayList<>();
for (int i = 0; i <= s.length(); i++) buckets.add(new ArrayList<>());
for (Map.Entry<Character, Integer> e : cnt.entrySet()) {
buckets.get(e.getValue()).add(e.getKey());
}
StringBuilder res = new StringBuilder();
for (int c = s.length(); c > 0; c--) {
for (char ch : buckets.get(c)) {
res.append(String.valueOf(ch).repeat(c));
}
}
return res.toString();
}
}class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> cnt;
for (char ch : s) cnt[ch]++;
vector<vector<char>> buckets(s.size() + 1);
for (auto& [ch, c] : cnt) {
buckets[c].push_back(ch);
}
string res;
for (int c = s.size(); c > 0; c--) {
for (char ch : buckets[c]) {
res.append(c, ch);
}
}
return res;
}
};func frequencySort(s string) string {
cnt := map[byte]int{}
for i := 0; i < len(s); i++ {
cnt[s[i]]++
}
buckets := make([][]byte, len(s)+1)
for ch, c := range cnt {
buckets[c] = append(buckets[c], ch)
}
res := []byte{}
for c := len(s); c > 0; c-- {
for _, ch := range buckets[c] {
for t := 0; t < c; t++ {
res = append(res, ch)
}
}
}
return string(res)
}var frequencySort = function(s) {
const cnt = new Map();
for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
const buckets = Array.from({ length: s.length + 1 }, () => []);
for (const [ch, c] of cnt) {
buckets[c].push(ch);
}
const res = [];
for (let c = s.length; c > 0; c--) {
for (const ch of buckets[c]) {
res.push(ch.repeat(c));
}
}
return res.join('');
};function frequencySort(s: string): string {
const cnt = new Map<string, number>();
for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
const buckets: string[][] = Array.from({ length: s.length + 1 }, () => []);
for (const [ch, c] of cnt) {
buckets[c].push(ch);
}
const res: string[] = [];
for (let c = s.length; c > 0; c--) {
for (const ch of buckets[c]) {
res.push(ch.repeat(c));
}
}
return res.join('');
}其他解法
按频率排序最直观；桶排序利用“次数不超过 n”的性质，免去比较排序。
解法 2：计数 + 按频率排序 时间 O(n + k log k)，空间 O(n + k)
先用哈希表统计每个字符的出现次数。再把所有不同字符按次数从大到小排序。最后依次把每个字符重复它的次数并拼接起来。k 为不同字符个数。
直接用库函数排序，代码最短。要多一个 k log k 的排序，但 k 很小时影响不大。
class Solution:
def frequencySort(self, s: str) -> str:
cnt = collections.Counter(s)
# 按出现次数从大到小排序字符
chars = sorted(cnt, key=lambda ch: -cnt[ch])
return ''.join(ch * cnt[ch] for ch in chars)class Solution {
public String frequencySort(String s) {
Map<Character, Integer> cnt = new HashMap<>();
for (char ch : s.toCharArray()) cnt.merge(ch, 1, Integer::sum);
List<Character> chars = new ArrayList<>(cnt.keySet());
chars.sort((a, b) -> cnt.get(b) - cnt.get(a));
StringBuilder res = new StringBuilder();
for (char ch : chars) {
int c = cnt.get(ch);
for (int i = 0; i < c; i++) res.append(ch);
}
return res.toString();
}
}class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> cnt;
for (char ch : s) cnt[ch]++;
vector<pair<char, int>> items(cnt.begin(), cnt.end());
sort(items.begin(), items.end(), [](const pair<char, int>& a, const pair<char, int>& b) { return a.second > b.second; });
string res;
for (auto& [ch, c] : items) res.append(c, ch);
return res;
}
};func frequencySort(s string) string {
cnt := map[byte]int{}
for i := 0; i < len(s); i++ {
cnt[s[i]]++
}
chars := make([]byte, 0, len(cnt))
for ch := range cnt {
chars = append(chars, ch)
}
sort.Slice(chars, func(i, j int) bool { return cnt[chars[i]] > cnt[chars[j]] })
res := make([]byte, 0, len(s))
for _, ch := range chars {
for k := 0; k < cnt[ch]; k++ {
res = append(res, ch)
}
}
return string(res)
}var frequencySort = function(s) {
const cnt = new Map();
for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
const chars = [...cnt.keys()].sort((a, b) => cnt.get(b) - cnt.get(a));
return chars.map(ch => ch.repeat(cnt.get(ch))).join('');
};function frequencySort(s: string): string {
const cnt = new Map<string, number>();
for (const ch of s) cnt.set(ch, (cnt.get(ch) || 0) + 1);
const chars = [...cnt.keys()].sort((a, b) => cnt.get(b)! - cnt.get(a)!);
return chars.map(ch => ch.repeat(cnt.get(ch)!)).join('');
}