LeetCode 面试题 16.02. 单词频率
题目描述
题意分析
用
book构造一个词频查询对象，之后可多次调用get(word)，返回该单词在书中出现的总次数，没有出现则返回 0。查询只读取统计结果，不会消耗或减少次数。
解法：哈希表统计词频（构造一次，多次查询）
核心思路
[!blue]
书的内容在构造后固定，每个单词的频次也随之固定。与其每次查询都遍历原数组，不如构造时一次统计完整频次，让所有查询复用同一张表。
用
freq[word]保存已经读过的部分中该单词的出现次数。初始没有读入任何单词，所有次数视为 0；每读到一次word就将其计数加 1，因此完整遍历后，表中的值恰好是全书词频。查询直接返回对应计数。Java 使用
getOrDefault(word, 0)，避免不存在的键得到空值；Go 读取不存在的整数映射键会得到零值 0。两者都自然覆盖未出现的单词，不必额外保存原书或为每次查询更新映射。
解题步骤
- 构造对象时初始化空频次表。
- 遍历
book中的每一次单词出现，在原频次上加 1。- 将频次表保存在对象中，供所有后续查询使用。
- 查询时返回对应频次，不存在则返回 0；重复查询同一个词会得到相同结果。
代码实现
class WordsFrequency {
private final Map<String, Integer> freq = new HashMap<>();
public WordsFrequency(String[] book) {
for (String word : book) {
// 构造时累加所有出现次数，查询时无需重扫书本。
freq.put(word, freq.getOrDefault(word, 0) + 1);
}
}
public int get(String word) {
return freq.getOrDefault(word, 0);
}
}
type WordsFrequency struct {
freq map[string]int
}
func Constructor(book []string) WordsFrequency {
f := make(map[string]int)
for _, w := range book {
// 构造时累加所有出现次数，查询时无需重扫书本。
f[w]++
}
return WordsFrequency{freq: f}
}
func (wf *WordsFrequency) Get(word string) int {
return wf.freq[word]
}
复杂度分析
设书中单词的总字符数为
S，不同单词数为u，查询单词长度为L。
- 时间复杂度：构造期望 $O(S)$，单次查询期望 $O(L+1)$，包含字符串哈希和比较的代价。
- 空间复杂度：不计输入字符串内容，频次表占 $O(u)$。表中保存字符串引用或字符串头及计数，不复制整本书的字符内容。
关键点总结
[!green]
- 固定数据上的多次查询，可以共用一次预处理结果。
- 每个单词出现一次就累计一次，映射中只有一个对应键。
- 构造后频次不再改变，查询缺失键按零处理。
易错点总结
[!yellow]
- 每次出现都直接写入 1，会覆盖已有次数，丢失重复出现的信息。
- Java 直接返回可能为
null的Integer，自动拆箱时会失败，应提供默认零。- 只保存出现多次的单词，会漏掉词频为 1 的合法结果。
- Go 必须先初始化映射再累加，不能向未初始化的映射写入。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 692. 前K个高频单词 | 中等 | 同样先统计完整词频，原题还排序取TopK，本题只按键返回次数。 |
| 244. 最短单词距离 II | 中等 | 同样一次预处理供多次查询，原题需保存位置列表，本题只需保存频次。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！