LeetCode 补充题 201. 字符串中第一个不重复的字符
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 387. 字符串中的第一个唯一字符
力扣限定非空小写字母串；本文同时支持大小写英文字母，并允许空串。
:::
给定仅含大小写英文字母的字符串
s，返回首个只出现一次的字符下标。区分大小写；不存在时返回
-1。
示例 1：
输入：
s = "aAbA"
输出：0
解释：a和A是不同字符，a只出现一次。
提示：
- 允许空串。
- 下标从
0开始。
题意分析
只出现一次需要检查整个字符串，第一个则需要保留原始下标顺序。把这两个要求分别交给计数和顺序扫描，可以避免在计数尚未完成时过早选定答案。
解法：频次统计 + 顺序扫描
核心思路
[!blue]
第一遍遍历把每个字符的总出现次数记入计数数组。输入只有大小写英文字母，ASCII 编码都小于 128，可以直接作为下标；大小写编码不同，自然分别计数。
第二遍从下标 0 向后扫描，遇到总频次为 1 的字符立即返回下标。完整计数保证该字符唯一，按原顺序扫描保证它是最早的一个。没有命中时统一返回 -1，空串也适用。
解题步骤
- 创建长度为 128 的计数数组，统计全部字符频次。
- 再次按原字符串下标递增扫描，找到频次为 1 的字符就返回下标。
- 扫描结束仍未找到则返回 -1。
代码实现
class Solution {
public int firstUniqChar(String s) {
int[] frequency = new int[128];
for (int i = 0; i < s.length(); i++) {
frequency[s.charAt(i)]++;
}
for (int i = 0; i < s.length(); i++) {
if (frequency[s.charAt(i)] == 1) {
return i;
}
}
return -1;
}
}
func firstUniqChar(s string) int {
frequency := [128]int{}
for i := 0; i < len(s); i++ {
frequency[s[i]]++
}
for i := 0; i < len(s); i++ {
if frequency[s[i]] == 1 {
return i
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
第一遍统计完整频次，第二遍按原顺序寻找频次为一的字符；用 ASCII 码直接索引计数数组。
易错点总结
[!yellow]
- 不能在第一遍遇到新字符时就返回，它可能在后面重复。
- 第二遍扫描原字符串，而不是扫描计数数组，否则得到的是编码最小的字符。
- 返回零基下标，且大小写不能合并计数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 387. 字符串中的第一个唯一字符 | 简单 | 都先统计频次，再按原顺序找首个唯一字符的下标；该题限定小写英文字母，本题允许大小写 ASCII 字符，并支持空串。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！