387. First Unique Character in a String

Posted on | In |

LeetCode 387. First Unique Character in a String

按照题意，我们考虑一种直观的解法。

  • 设置一个大小为26的int数组charCount，用来记录每个字符出现的次数。

  • 第一次遍历字符串，对于每一个字符c，将charCount[c - 'a']自增1。

  • 第二次遍历字符串，对于每一个下标i，如果该位置的字符对应的计数值为1，我们知道在整个字符串中这个字符只出现了一次，范围这个下标i即可。

对应代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
public int firstUniqChar(String s) {
    int[] charCount = new int[26];
    for (int i = 0; i < s.length(); i++) {
        charCount[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < s.length(); i++) {
        if (charCount[s.charAt(i) - 'a'] == 1) {
            return i;
        }
    }
    return -1;
}

上面的方法，遍历两边输入的字符串，时间复杂度是O(n)。考虑字符串很长但是字典很小的情况，我们可以做到只遍历一次字符串，然后遍历一次count数组，其中count数组的大小正比于字典长度。虽然这种方法的渐进时间复杂度也是O(n)，但是在字符串很长的情况下性能更好。

具体方法如下。

  • 设置一个大小为26*2的int[][]数组charCount。其中int[i][0]表示对应int值为i的字符首次出现的位置，int[i][1]表示值为i的字符在字符串中出现的次数。

  • 遍历字符串，填充charCount。

  • 遍历charCount，找到并返回出现次数为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
public int firstUniqChar(String s) {
    int[][] charCount = new int[26][];
    for (int i = 0; i < charCount.length; i++) {
        charCount[i] = new int[2];
        charCount[i][0] = -1;
    }
    for (int i = 0; i < s.length(); i++) {
        int[] charCountI = charCount[s.charAt(i) - 'a'];
        if (charCountI[0] == -1) {
            charCountI[0] = i;
            charCountI[1] = 1;
        } else {
            charCountI[1]++;
        }
    }
    int minPos = s.length();
    for (int i = 0; i < charCount.length; i++) {
        if (charCount[i][1] == 1) {
            if (charCount[i][0] < minPos) {
                minPos = charCount[i][0];
            }
        }
    }
    if (minPos == s.length()) {
        return -1;
    } else {
        return minPos;
    }
}