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

约 5 分钟
文章信息 10 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 腾讯 华为 网易
标签
字符串 哈希表 排序 堆（优先队列） 计数 桶排序
目录

题目描述

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

image-20250420095247005

题意分析

输入一个字符串，输出它的一个重新排列，使得字符按出现频率从高到低排布。所谓「按频率排布」，指的是同一个字符的所有副本必须挨在一起，且出现次数多的字符整体排在出现次数少的字符前面。

有两个宽松之处需要读出来。其一，同频字符之间的先后顺序不作要求，也就是说这题有多个合法答案，判题是特判式的，不必为了对齐某个「标准输出」去补充二级排序规则。其二，输出必须是原串的排列，长度和各字符的个数都要和输入完全一致，不能只输出「去重后的字符」。

字符集是大小写英文字母和数字，共 62 种，且大小写敏感——'A' 和 'a' 是两个不同的字符，各自计数。而字符串长度可以到 $5 \times 10^5$。这一长一短的对比是本题最重要的约束信号：待排序的「不同字符」最多只有 62 个，而字符串长度是它的上万倍。任何把排序作用在「每个字符位置」上的做法，都是在为一个规模仅 62 的问题付出规模 $5 \times 10^5$ 的代价。

需要单独确认的边界：整串只有一种字符（原样返回即可）；所有字符频次都相同（任意顺序都合法）；只有一个字符；以及频次可能大到接近字符串长度，用它做减法比较时要留意会不会溢出。

解法：频次统计后排序不同字符

核心思路

直接排序字符串中的全部 $n$ 个位置需要 $O(n\log n)$，但真正需要比较的只有不同字符。先统计频次，再对 $k$ 个不同字符按频次降序排序，最后按各自频次展开即可。

构造过程的不变量是：已经写入结果的每种字符，其数量与输入频次完全一致；未写入字符仍完整保存在计数数组中。因此最终结果必然是原字符串的一个排列。

题目允许同频字符采用任意顺序，所以比较器只需比较频次，不需要额外的字典序规则。字符集只有大小写字母和数字，用长度 128 的数组即可直接按字符编码计数。

解题步骤

  1. 扫描字符串，统计每个字符的频次。
  2. 收集所有频次大于 0 的字符。
  3. 将这些不同字符按频次从高到低排序。
  4. 按排序结果，把每个字符重复追加对应次数。

例如 tree 的频次为 e:2、t:1、r:1，排序后先展开 e，可得到 eetr 或 eert，两者都合法。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public String frequencySort(String s) {
        int[] count = new int[128];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }

        List<Character> chars = new ArrayList<>();
        for (char ch = 0; ch < count.length; ch++) {
            if (count[ch] > 0) {
                chars.add(ch);
            }
        }
        chars.sort((first, second) -> Integer.compare(count[second], count[first]));

        StringBuilder result = new StringBuilder(s.length());
        for (char ch : chars) {
            result.append(String.valueOf(ch).repeat(count[ch]));
        }
        return result.toString();
    }
}

import "sort"

func frequencySort(s string) string {
    count := [128]int{}
    for i := 0; i < len(s); i++ {
        count[s[i]]++
    }

    chars := make([]byte, 0, 62)
    for ch, frequency := range count {
        if frequency > 0 {
            chars = append(chars, byte(ch))
        }
    }
    sort.Slice(chars, func(i int, j int) bool {
        return count[chars[i]] > count[chars[j]]
    })

    result := make([]byte, 0, len(s))
    for _, ch := range chars {
        for times := count[ch]; times > 0; times-- {
            result = append(result, ch)
        }
    }
    return string(result)
}

复杂度分析

  • 时间复杂度：$O(n+k\log k)$，其中 $k$ 是不同字符数；本题 $k$ 最多为 62。
  • 空间复杂度：$O(n+k)$，主要是返回结果和不同字符列表；不计返回值时为 $O(k)$。

关键点总结

  • 应排序 $k$ 个不同字符，而不是排序 $n$ 个字符位置。
  • 同频字符顺序任意，测试时不能只接受某一种输出。
  • 输出时必须按频次完整展开，保证字符数量不变。
  • 若字符集很大且要求严格线性时间，可按频次使用桶排序；本题排序至多 62 个字符更简单。

易错点总结

  • 比较器方向写反会得到频次升序结果。
  • 只输出去重后的字符，会使结果长度和字符数量都不正确。
  • 把大小写合并，或只按 26 个小写字母计数，会改变输入字符构成。
  • Go 创建字符切片时长度应为 0、容量为 $k$；否则前面会残留零值字节。

相似题目

题目 难度 考察点
242. 有效的字母异位词 简单 频次相等判定
347. 前 K 个高频元素 中等 前 K 高频的堆与桶排序
387. 字符串中的第一个唯一字符 简单 首个唯一字符定位
692. 前K个高频单词 中等 频次相同再按字典序
1636. 按照频率将数组升序排序 简单 频次升序的多级比较