LeetCode387-字符串中的第一个唯一字符

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/first-unique-character-in-a-string/

中文链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/

题目详述

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

案例:

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

s = "loveleetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

题目详解

  • 第一次遍历，统计出各个字符出现的次数。
  • 第二次遍历，返回第一次字符个数为 1 的索引即可；若不存在按题目要求返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode_00387 {

    public int firstUniqChar(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        for (int i = 0; i < s.length(); ++i) {
            if (cnt[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}

若输入的字符串很长，按照上面的思路可能导致第二次遍历很久才能找到答案。可以换一种思路，把第二次遍历的迭代次数固定在 26 次。

  • 同样是新建一个数组 index，不过数组不用来统计各个字符出现的次数，而是用来记录各个字符出现的下标。
  • 初始化数组各个元素为 -1。
  • 当第一次碰到该字符时，把该字符对应下标记录在索引数组中。
  • 当再次碰到该字符时，把该字符记录在索引数组中的元素改为 -2。
  • 当遍历完成后，出现 0 次的字符对应的索引数组元素为 -1。
  • 出现 1 次的字符对应的索引数组元素是它的下标。
  • 出现 2 次及以上的字符为对应的索引数组元素为 -2。
  • 最后统计索引数组中大于或等于 0 的元素的最小值即可，若不存在按题目要求返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00387 {

    public int firstUniqChar(String s) {
        int[] index = new int[26];
        Arrays.fill(index, -1);
        for (int i = 0; i < s.length(); ++i) {
            int j = s.charAt(i) - 'a';
            if (index[j] == -1) {
                index[j] = i;
            } else if (index[j] >= 0) {
                index[j] = -2;
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < 26; ++i) {
            if (index[i] >= 0) {
                res = Math.min(res, index[i]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}