leetcode387字符串中的第一个唯一字符(String)

题目

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

示例

1
2
3
4
5
s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

题解

方法一使用暴力法,算法复杂度O(n^2);

方法二使用HashMap来存储字符串中每个字符出现的次数, 然后一次遍历即可实现, 算法复杂度:O(n);

方法三使用一个包含26个元素的数组便可完成个数统计,首先使用数组count记录每个字母出现的次数,然后取出最先出现次数为1的字母的下标。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class solution{
//方法一:暴力法
public int firstUniqChar(String s) {
char[] chars = s.toCharArray();
for(int i=0;i<chars.length;i++){
boolean isUnique = true;
for(int j=0;j<chars.length;j++){
if(i!=j&&chars[i]==chars[j]){
isUnique = false;
break;
}
}
if(isUnique) return i;
}
return -1;
}
//方法二:Map
public int firstUniqChar2(String s) {
Map<Character,Integer> map = new HashMap<>(s.length());
for(char ch: s.toCharArray()){
if(map.containsKey(ch)){
map.put(ch,map.get(ch)+1);
}else{
map.put(ch,1);
}
}
for(int i=0;i<s.length();i++){
if(map.get(s.charAt(i))==1) return i;
}
return -1;
}
//方法三:使用一个26个字母的数组来计数
public int firstUniqChar3(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 i;
}
return -1;
}
}