LeetCode 补充题 199. 前 K 个高频单词及词频
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 692. 前 K 个高频单词
LeetCode 原题仅返回单词，输入为小写英文字母；本文同时返回十进制词频字符串，并允许数字和大小写英文字母。两题的频次及同频排序规则一致。
:::
给定由数字和大小写英文字母组成的字符串数组
words和整数k，返回频次最高的k个单词及各自频次，频次降序，同频时单词字典序升序。每项用两个字符串
[单词, 十进制频次]表示。
示例 1：
输入：
words = ["b","a","b"], k = 2
输出：[["b","2"],["a","1"]]
提示：
1 <= k <= 不同单词数- 单词非空。
题意分析
排名对象是不同单词，每个单词的优先级先由出现次数决定，再由字典序打破平局。因此应先完成计数，再对去重后的单词排序，最后补上对应的十进制频次。
解法：哈希计数 + 双关键字排序
核心思路
[!blue]
用哈希表累计每个单词的出现次数，随后只取表中的不同单词作为排序对象。计数在排序开始前已经固定，比较器读取同一份频次表。
比较两个单词时，频次不等则让频次高的排在前面；频次相等才比较单词本身，让字典序小的排在前面。这两个关键字的方向不同，不能整体反转升序结果。
排序后前 k 个单词恰好满足排名要求。逐个输出单词和从计数表读取的频次，并将频次转为字符串，确保结果每项都是两个字符串。
解题步骤
- 遍历 words，统计每个单词的频次。
- 收集不同单词，按频次降序、同频字典序升序排序。
- 取前 k 项，分别生成单词及十进制频次字符串组成的结果项。
代码实现
class Solution {
public List<List<String>> topKFrequent(String[] words, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String word : words) {
freq.put(word, freq.getOrDefault(word, 0) + 1);
}
List<String> unique = new ArrayList<>(freq.keySet());
unique.sort(
(first, second) -> {
int countCompare = Integer.compare(freq.get(second), freq.get(first));
if (countCompare != 0) {
return countCompare;
}
return first.compareTo(second);
});
List<List<String>> result = new ArrayList<>();
for (String word : unique.subList(0, k)) {
result.add(Arrays.asList(word, Integer.toString(freq.get(word))));
}
return result;
}
}
import (
"sort"
"strconv"
)
func topKFrequent(words []string, k int) [][]string {
freq := make(map[string]int)
for _, word := range words {
freq[word]++
}
unique := make([]string, 0, len(freq))
for word := range freq {
unique = append(unique, word)
}
sort.Slice(unique, func(i, j int) bool {
if freq[unique[i]] != freq[unique[j]] {
return freq[unique[i]] > freq[unique[j]]
}
return unique[i] < unique[j]
})
result := make([][]string, 0, k)
for _, word := range unique[:k] {
result = append(result, []string{
word,
strconv.Itoa(freq[word]),
})
}
return result
}
复杂度分析
- 时间复杂度：设输入词数为 $n$、不同词数为 $u$、最大词长为 $L$，时间 $O(nL+uL\log u)$。
- 空间复杂度：额外空间 $O(uL)$。
关键点总结
[!green]
先统计单词频次，再按频次降序、字典序升序排序不同单词；输出时从同一计数表取出频次。
易错点总结
[!yellow]
- 相同频次时按字典序升序，不能沿用频次的降序方向。
- 大小写保留原样，不能先转小写合并计数。
- 输出频次是字符串，不是整数；每个不同单词只输出一次。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 692. 前K个高频单词 | 中等 | 词频降序、同频字典序升序的规则相同；该题仅返回单词，本题还返回十进制词频字符串，并扩展允许的字符范围。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！