LeetCode 补充题 147. 指定频次下首次出现最晚的单词
题目描述
给定单词序列
words和正整数n，返回恰好出现n次的单词中，首次出现位置最靠后的那个。单词区分大小写；不存在符合条件的单词时，返回空字符串。
示例 1：
输入：
words = ["python","Java","cpp","go","java","go","cpp"], n = 2
输出："go"
解释：cpp、go都出现两次，go首次出现在下标 3，晚于cpp的下标 2。Java 与java大小写不同。
示例 2：
输入：
words = ["cpp","go","go","cpp"], n = 2
输出："go"
解释： 两词都出现两次，但go的首次位置更靠后；如果按最后出现位置选择，反而会得到cpp。
提示：
- 本篇选用如下平局规则：“靠后”比较第一次出现的位置。
- 相同单词后续重复的位置不改变其优先级。
题意分析
频次必须恰好为
n，扫描途中出现过n次不代表最终仍合格。先得到完整频次，再按首次出现位置选最靠后的词，能避免把最后出现位置或字典序误当排序依据。
解法：频次筛选与首次位置扫描
核心思路
[!blue]
第一遍用
counts统计每个单词的总次数。第二遍从左到右扫描，只有seen尚未记录的词才处理，随后立即标记，使该词的所有后续重复位置都不能影响优先级。遇到总次数等于
n的首次出现时覆盖答案。因为这些首次位置按递增顺序被处理，每次覆盖都比此前候选更靠后，扫描结束的最后一次覆盖就是目标。哈希表按原字符串区分大小写，不进行转换。没有合格词时始终保留初始空串，且无需对全部不同单词额外排序。
解题步骤
- 先统计全部单词总次数。
- 再次从左到右扫描，用集合只处理每个词的第一次出现。
- 频次符合时覆盖答案，最后一次覆盖即首次位置最靠后者。
代码实现
class Solution {
public String latestFirstWord(String[] words, int n) {
Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
counts.merge(word, 1, Integer::sum);
}
Set<String> seen = new HashSet<>();
String out = "";
for (String word : words) {
if (seen.add(word) && counts.get(word) == n) {
out = word;
}
}
return out;
}
}
func latestFirstWord(words []string, n int) string {
counts := map[string]int{}
for _, word := range words {
counts[word]++
}
seen := map[string]bool{}
out := ""
for _, word := range words {
if !seen[word] {
seen[word] = true
if counts[word] == n {
out = word
}
}
}
return out
}
复杂度分析
- 时间复杂度：期望 $O(C)$。
- 空间复杂度：额外空间 $O(C)$，C 为输入单词总字符数。
关键点总结
[!green]
必须先得到完整频次，再按首次位置选择；最后一次出现的位置不能替代首次位置。
易错点总结
[!yellow]
如果误用最后出现位置，给定示例会选 cpp，得到与示例不符的结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 387. 字符串中的第一个唯一字符 | 简单 | 同样先统计频次再按位置选择，原题找最早的唯一字符，本题找指定频次中首次位置最靠后者。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！