当前位置 博文首页 > 天天搬砖的程序员博客：LeetCode 387. 字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例：
s = "leetcode"
返回 0
s = "loveleetcode"
返回 2
**提示：**你可以假定该字符串只包含小写字母。
public int firstUniqChar(String s) {
// 统计每个字符出现的次数
Map<Character, Integer> timesCountMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
Integer times = timesCountMap.getOrDefault(s.charAt(i), 0);
times++;
timesCountMap.put(s.charAt(i), times);
}
// 返回第一个只出现一次的字符
for (int i = 0; i < s.length(); i++) {
Integer times = timesCountMap.getOrDefault(s.charAt(i), 0);
if (times == 1) {
return i;
}
}
return -1;
}
复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要进行两次遍历。
空间复杂度：O(m)，m <= 26（只包含小写字母）。
算法写法细节小优化
public int firstUniqChar(String s) {
// 统计每个字符出现的次数
int length = s.length();
Map<Character, Integer> timesCountMap = new HashMap<>();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
Integer times = timesCountMap.getOrDefault(ch, 0);
times++;
timesCountMap.put(ch, times);
}
// 返回第一个只出现一次的字符
for (int i = 0; i < length; i++) {
if (timesCountMap.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
从复杂度来看，优化空间不大了，不过参考官方题解，可以优化第二次遍历的数据规模，上述算法中两次遍历的数据规模都是字符串所有字符
官方题解提供了一个优化思路：
1.先遍历一次，记录字符首次出现的索引，若再次出现，将索引置为-1
2.遍历哈希，看是否不等于-1的索引，并且取其中的最小值
public int firstUniqChar(String s) {
int length = s.length();
Map<Character, Integer> charIndexMap = new HashMap<>();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (charIndexMap.containsKey(ch)) {
charIndexMap.put(ch, -1);
} else {
charIndexMap.put(ch, i);
}
}
int firstIndex = length;
for (Map.Entry<Character, Integer> entry : charIndexMap.entrySet()) {
int pos = entry.getValue();
if (pos != -1 && pos < firstIndex) {
firstIndex = pos;
}
}
if(firstIndex == length) {
firstIndex = -1;
}
return firstIndex;
}
