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

摘要

这道题看起来很简单：
统计字符出现次数，然后按次数排序。

但如果你真在工程里做过类似的事，比如：

• 搜索关键词权重排序
• 日志里统计最常出现的错误码
• 文本分析中提取高频字符或 Token

你会发现这类问题的核心，其实是「频率统计 + 排序策略」。

LeetCode 451 正好是一个非常干净、非常标准的模板题，非常适合用来练：

• 字符统计
• 排序规则设计
• Swift 中 Dictionary + Array 的组合用法

描述

题目给你一个字符串s，要求你：

• 统计每个字符在字符串中出现的次数
• 按出现频率从高到低排序
• 相同字符必须放在一起
• 如果频率相同，字符之间的相对顺序不重要

需要注意的几个点：

• 大写字母和小写字母是不同字符
• 字符串长度最大可以到5 * 10^5
• 所以实现不能太“暴力”

题解答案（整体思路）

这道题的解法其实非常清晰，可以拆成三步：

第一步：统计字符频率

遍历字符串，用一个字典：

[Character:Int]

来记录每个字符出现的次数。

第二步：按频率排序

把字典转成数组：

[(Character,Int)]

然后按value（出现次数）做降序排序。

第三步：按排序结果拼接字符串

排序完成后，按顺序把字符重复count次，拼接成最终字符串。

题解代码（Swift 可运行 Demo）

下面是完整、可直接运行的 Swift 实现：

classSolution{funcfrequencySort(_s:String)->String{// 1. 统计字符频率varfreq:[Character:Int]=[:]forchins{freq[ch,default:0]+=1}// 2. 按出现次数降序排序letsorted=freq.sorted{$0.value>$1.value}// 3. 构造结果字符串varresult=""for(ch,count)insorted{result+=String(repeating:ch,count:count)}returnresult}}

题解代码分析

1. 为什么用 Dictionary 统计？

varfreq:[Character:Int]=[:]

这是最自然、也最直观的方式：

• key是字符
• value是出现次数

Swift 的Dictionary对这种计数场景支持得非常友好。

2. 排序这一步在干什么？

letsorted=freq.sorted{$0.value>$1.value}

sorted之后的数据结构其实是：

[(Character,Int)]

也就是一个(字符, 次数)的数组。

排序规则很简单：

• 谁出现次数多，谁排前面

3. 为什么不能一边统计一边排序？

因为：

• 统计是 O(n)
• 排序是 O(k log k)，k 是不同字符数量

混在一起只会让逻辑变复杂，不会更快。

4. 字符拼接这一步为什么这样写？

result+=String(repeating:ch,count:count)

这一步非常直观：

• 一个字符出现几次，就拼接几次
• 保证相同字符一定是连续的

同时也满足了题目「相同字母必须放在一起」的要求。

示例测试及结果

示例 1

letsolution=Solution()print(solution.frequencySort("tree"))

输出可能是：

eert

或者：

eetr

都是正确结果。

示例 2

print(solution.frequencySort("cccaaa"))

输出：

cccaaa

或者：

aaaccc

示例 3

print(solution.frequencySort("Aabb"))

输出：

bbAa

注意这里：

• 'A'和'a'是不同字符
• 大小写不会混在一起

实际场景结合

这道题的模式在实际开发中非常常见，比如：

• 搜索系统里，统计关键词出现频率
• 日志分析中，找最常见的错误类型
• 文本分析中，做简单的词频或字符分布

把这套逻辑稍微改一下，就可以变成：

• Top K 高频元素
• 热词统计
• 标签权重排序

时间复杂度

• 统计频率：O(n)
• 排序（字符种类数为 k）：O(k log k)
• 构造字符串：O(n)

总体时间复杂度：

O(n + k log k)

在实际情况下，k通常远小于n。

空间复杂度

• 字典存储频率：O(k)
• 排序数组：O(k)
• 结果字符串：O(n)

空间复杂度：

O(n + k)

总结

LeetCode 451 是一道非常「工程友好」的题：

• 思路清晰
• 模板性强
• 非常适合拿来练 Swift 的集合操作