LeetCode 451. 根据字符出现频率排序

Categories:

题目描述
思路分析
1. 解法一：桶排序（推荐）
相似题目

题目描述

✅ 451. 根据字符出现频率排序

思路分析

解法一：桶排序（推荐）

核心思路：

统计每个字符出现次数，并记录最大频次。

频次作为桶索引，桶中存放重复字符。

从高频到低频拼接答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(n)，桶数组与结果占用线性空间。

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> cnt = new HashMap<>();
        int maxFreq = 0;
        for (char c : s.toCharArray()) {
            int v = cnt.getOrDefault(c, 0) + 1;
            cnt.put(c, v);
            maxFreq = Math.max(maxFreq, v);
        }

        List<StringBuilder> buckets = new ArrayList<>(maxFreq + 1);
        for (int i = 0; i <= maxFreq; i++) {
            buckets.add(new StringBuilder());
        }

        // 按频次把字符放入桶中
        for (Map.Entry<Character, Integer> e : cnt.entrySet()) {
            char c = e.getKey();
            int f = e.getValue();
            StringBuilder sb = buckets.get(f);
            for (int i = 0; i < f; i++) {
                sb.append(c);
            }
        }

        StringBuilder res = new StringBuilder();
        for (int f = maxFreq; f >= 1; f--) {
            res.append(buckets.get(f));
        }

        return res.toString();
    }
}

func frequencySort(s string) string {
	cnt := make(map[byte]int)
	maxFreq := 0
	for i := 0; i < len(s); i++ {
		cnt[s[i]]++
		if cnt[s[i]] > maxFreq {
			maxFreq = cnt[s[i]]
		}
	}

	buckets := make([][]byte, maxFreq+1)

	// 按频次把字符放入桶中
	for ch, f := range cnt {
		for i := 0; i < f; i++ {
			buckets[f] = append(buckets[f], ch)
		}
	}

	res := make([]byte, 0, len(s))
	for f := maxFreq; f >= 1; f-- {
		res = append(res, buckets[f]...)
	}

	return string(res)
}

相似题目

题目	难度	考察点
347. 前 K 个高频元素	中等	哈希 + 堆/桶
692. 前 K 个高频单词	中等	堆
387. 字符串中的第一个唯一字符	简单	计数
242. 有效的字母异位词	简单	计数
451. 根据字符出现频率排序	中等	桶排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/00083753