0451. 根据字符出现频率排序【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 桶排序

1. 📝 题目描述

• leetcode

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

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

---

示例 1：

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

示例 2：

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

示例 3：

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

---

提示：

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

2. 🎯 s.1 - 桶排序

c

char* frequencySort(char* s) {
    int freq[128] = {0};
    int len = strlen(s);
    for (int i = 0; i < len; i++) freq[(unsigned char)s[i]]++;
    // 桶排序
    char* res = (char*)malloc(len + 1);
    int idx = 0;
    for (int f = len; f > 0; f--) {
        for (int c = 0; c < 128; c++) {
            if (freq[c] == f) {
                for (int k = 0; k < f; k++) res[idx++] = (char)c;
            }
        }
    }
    res[idx] = '\0';
    return res;
}

js

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
  const freq = new Map()
  for (const ch of s) freq.set(ch, (freq.get(ch) || 0) + 1)
  // 桶排序
  const buckets = Array.from({ length: s.length + 1 }, () => [])
  for (const [ch, cnt] of freq) buckets[cnt].push(ch)
  let res = ''
  for (let i = buckets.length - 1; i > 0; i--) {
    for (const ch of buckets[i]) res += ch.repeat(i)
  }
  return res
}

py

class Solution:
    def frequencySort(self, s: str) -> str:
        freq = Counter(s)
        buckets = [[] for _ in range(len(s) + 1)]
        for ch, cnt in freq.items():
            buckets[cnt].append(ch)
        res = []
        for i in range(len(buckets) - 1, 0, -1):
            for ch in buckets[i]:
                res.append(ch * i)
        return ''.join(res)

• 时间复杂度：$O(n+|\mathrm{\Sigma }|)$
• 空间复杂度：$O(n+|\mathrm{\Sigma }|)$

算法思路：

• 统计每个字符的出现频率
• 以频率为索引放入桶中，从高到低遍历桶拼接结果