LeetCode 剑指 Offer 50. 第一个只出现一次的字符
题目描述
题意分析
在字符串中找一个字符：它在整个字符串里总共只出现一次，而且在所有满足这一条件的字符中，出现位置最靠前。返回的是字符本身，不是它的下标；如果没有这样的字符，按题目约定返回空格
' '。“第一个”和“只出现一次”是两个条件。前者按原字符串的位置判断，不是按字母表顺序；后者必须查看整个字符串，某个字符在当前前缀中只出现一次，并不代表后面不会再次出现。空字符串同样返回空格。
解法：频次数组 + 原序扫描
核心思路
[!blue]
先解决“是否唯一”，再解决“谁最靠前”。第一遍扫描完整字符串，记录每种字符的总出现次数。只有频次确定后，才能可靠地判断一个字符是否只出现一次。
本题字符串只包含小写英文字母，用长度为
26的数组即可记录频次。字符c对应下标c - 'a'，相同字符总是更新同一个位置，不需要保存它每次出现的下标。第二遍重新按原顺序扫描字符串。遇到频次为一的字符就立即返回：它满足唯一性，且所有更早的位置都已经检查过，不符合要求，因此它一定是第一个符合条件的字符。
如果第二遍没有返回，说明每个实际出现的字符都重复了；空字符串则两遍循环都不执行。这两种情况统一走到末尾返回空格，不需要单独分支。
解题步骤
- 创建长度为
26、初始全为零的频次数组count。- 扫描完整字符串，对每个字符执行
count[c - 'a']++。- 再次从字符串开头扫描，查询当前字符的完整频次。
- 遇到频次为一的字符立即返回它；遍历结束仍未找到时返回空格。
代码实现
class Solution {
public char firstUniqChar(String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
// 频次已完整统计，按原顺序找才能确定第一个唯一字符。
if (count[s.charAt(i) - 'a'] == 1) {
return s.charAt(i);
}
}
return ' ';
}
}
func firstUniqChar(s string) byte {
count := [26]int{}
for i := 0; i < len(s); i++ {
count[s[i]-'a']++
}
for i := 0; i < len(s); i++ {
// 频次已完整统计，按原顺序找才能确定第一个唯一字符。
if count[s[i]-'a'] == 1 {
return s[i]
}
}
return ' '
}
复杂度分析
- 时间复杂度：
O(n)，其中n是字符串长度。第一遍统计全部字符，第二遍最多再扫描一次。- 空间复杂度：
O(1)。频次数组固定为26项，不随字符串长度增长。
关键点总结
[!green]
- 完整频次决定唯一性，原序扫描决定先后顺序，两遍扫描各自解决一个条件。
- 第一次扫描还不知道后缀内容，不能根据暂时出现一次就提前返回。
- 字符种类固定，可以直接用数组建立字符到次数的映射。
易错点总结
[!yellow]
- 按频次数组顺序找答案：这样得到的是字母顺序最小的唯一字符，未必是在原串最早出现的字符。
- 第一遍计数为一就返回：后续还可能再次出现该字符，必须先统计完整频次。
- 只判断当前位置与相邻字符是否不同：重复字符不一定相邻，唯一性需要看全串。
- 返回下标或其他默认值：接口要求返回字符，无答案时是空格
' '，不是数字零、空字符串或null。- 把空串当作异常：没有候选字符时直接使用统一的空格返回值即可。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 383. 赎金信 | 简单 | 同样先按字符累计频次，本题再结合原顺序定位首个频次为1的位置。 |
| 451. 根据字符出现频率排序 | 中等 | 原题按频次重新排列字符，本题保留原出现顺序并只找唯一字符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！