LeetCode 387. 字符串中的第一个唯一字符
题目描述
题意分析
返回字符串中最靠前的、在整个字符串里只出现一次的字符下标；不存在则返回
-1。这里的“第一个”按原字符串位置判断，不是按字母顺序判断。题目只包含小写英文字母，可以用长度为 26 的数组计数。
解法：两次遍历计数
核心思路
[!blue]
判断一个字符是否唯一，必须知道它在整个字符串中的出现次数。第一次遇到它时只能确认“目前出现一次”，后面仍可能重复，因此先完整扫描字符串，将字符
c的次数记录在frequency[c - 'a']中。计数完成后，再按下标从小到大扫描。若当前位置的字符频次为 1，它就是全局唯一字符；之前的位置都已检查过且不符合条件，所以第一次命中的下标必然是题目要求的最小下标，可以立即返回。
若第二次扫描结束仍未命中，说明所有字符都出现多次，返回
-1。两次遍历分别解决“是否唯一”和“是否最早”，不需要排序，也不用额外记录每个字符的位置。
解题步骤
- 创建长度为 26、初始全为 0 的计数数组
frequency。- 第一次遍历字符串，用当前字符减去
'a'得到计数下标，将对应次数加一。- 第二次从下标 0 开始遍历；若当前字符的总频次为 1，返回当前字符串下标。
- 全部位置都不符合时返回
-1。Java 的
charAt(i)和 Go 的s[i]在本题小写英文字母范围内都能直接取得当前字符，返回的i就是所需位置。
代码实现
class Solution {
public int firstUniqChar(String s) {
int[] frequency = new int[26];
// 先收集完整频次，避免过早判断唯一
for (int i = 0; i < s.length(); i++) {
frequency[s.charAt(i) - 'a']++;
}
// 再按原顺序返回首个全局唯一字符的下标
for (int i = 0; i < s.length(); i++) {
if (frequency[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}
}
func firstUniqChar(s string) int {
frequency := [26]int{}
// 先收集完整频次，避免过早判断唯一
for i := 0; i < len(s); i++ {
frequency[s[i]-'a']++
}
// 再按原顺序返回首个全局唯一字符的下标
for i := 0; i < len(s); i++ {
if frequency[s[i]-'a'] == 1 {
return i
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是字符串长度，两次扫描最多各访问 $n$ 个字符。
- 空间复杂度：$O(1)$，计数数组始终只有 26 项。
关键点总结
[!green]
- 完整频次保证“只出现一次”，原串顺序保证“第一个”。
- 字符减去
'a'得到的是计数数组下标，最终返回的是它在字符串中的下标。
易错点总结
[!yellow]
- 第一次遇到字符就判断唯一，会漏掉它在后面重复出现的情况。
- 按 26 个字母的顺序检查计数，会找到字母序最小的唯一字符，不能保证位置最早。
- 没有答案必须返回
-1，因为 0 本身也是合法答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 383. 赎金信 | 简单 | 同样先按字符累计频次，本题再结合原顺序定位首个频次为1的位置。 |
| 451. 根据字符出现频率排序 | 中等 | 原题按频次重新排列字符，本题保留原出现顺序并只找唯一字符。 |
| 补充题 201. 字符串中第一个不重复的字符 | 简单 | 区分大小写的首个唯一字符。 |
| 补充题 141. 字符流中第一个不重复的字符 | 中等 | 都维护每个字符的出现次数；补充题在每次插入后查询当前首个唯一字符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！