LeetCode 补充题 139. 字符出现次数统计
题目描述
:::fold-green 相关原题
牛客原题： ✅ 字符串字符统计
牛客原题要求忽略空白字符，并以非空字符串为输入；本文统计所有 Unicode 码点，包含空白字符，也允许空串。
:::
给你一个 Unicode 字符串
s，请按 Unicode 码点统计每个字符的出现次数，返回字符到次数的映射，输出顺序不限。不要按 UTF-8 字节或单个 UTF-16 代码单元计数。组合字形中的多个码点分别统计。
示例 1：
输入：
s = "中a中😀"
输出：{"中":2,"a":1,"😀":1}
解释： 按 Unicode 码点统计，😀 计为一个字符，映射输出顺序不限。
提示：
- 按 Unicode 码点统计，不按 UTF-8 字节或 UTF-16 单个代码单元统计。
- 映射顺序不限。
- 组合字形的不同码点分别计数。
题意分析
逐个 Unicode 码点统计次数。Java 的映射键为码点整数，Go 的键为 rune；示例用该码点对应的字符展示键。一个补充平面字符仍只计一次，组合字形中的多个码点分别统计。
解法：按 Unicode 码点累计频次
核心思路
[!blue]
哈希表
counts[c]表示已经扫描的前缀中，码点c出现了多少次。每读到一个码点，就把对应计数加 1；首次出现按 0 开始，扫描结束后即得到整个字符串的频率表。Java 的
codePoints()将代理对作为一个码点输出，merge负责初始化或累加；Go 的range按 UTF-8 解码出rune，映射未出现的键默认计数为 0。两者都不会把编码单元数误当出现次数。空白和标点同样进入计数，不做过滤、大小写转换或 Unicode 归一化。组合字形包含多个码点时分别统计，空串则返回空映射。
解题步骤
- 按码点遍历输入，不能把补充平面字符拆成两个 UTF-16 单元或多个 UTF-8 字节。
- 以码点值为键，首次出现从 0 开始累计。
- 返回映射，展示时可把码点键转换回对应字符。
代码实现
class Solution {
public Map<Integer, Integer> frequencies(String s) {
Map<Integer, Integer> counts = new HashMap<>();
s.codePoints().forEach(c -> counts.merge(c, 1, Integer::sum));
return counts;
}
}
func frequencies(s string) map[rune]int {
counts := map[rune]int{}
for _, c := range s {
counts[c]++
}
return counts
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(u)$，u为不同码点数。
关键点总结
[!green]
字符的编码宽度与出现次数无关；频率表按码点区分，组合字形不自动合并成一个键。
易错点总结
[!yellow]
Java的char和Go的byte都不能代表任意Unicode字符；这里按码点，不按用户感知的字形簇统计。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 387. 字符串中的第一个唯一字符 | 简单 | 频率表可作为寻找首次唯一字符的预处理；本题支持任意码点，不局限于小写字母数组。 |
| 451. 根据字符出现频率排序 | 中等 | 在本题频次统计后再按频率排序，即得到按出现频率组织字符的输出。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！