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;
    }
}