LeetCode：387. 字符串中的第一個惟一字符

387. 字符串中的第一個惟一字符 數組

給定一個字符串，找到它的第一個不重複的字符，並返回它的索引。若是不存在，則返回 -1。spa

 

示例：code

s = "leetcode"
返回 0blog

s = "loveleetcode"
返回 2
 索引

提示：你能夠假定該字符串只包含小寫字母。leetcode

連接：https://leetcode-cn.com/problems/first-unique-character-in-a-string字符串

思路：get

1.定義長度爲123(方法1)或27(方法2)的字符數組sArraystring

2.先遍歷字符串s，將其中每一個字符的ASCII碼值做爲下標index，將sArray[index]的值累加，index++class

3.再順序遍歷一遍字符串s，在字符數組sArray中找到第一個sArray[(int)s[i]]等於1的字符，並返回

時間複雜度：O(n)    O(n) + O(n) ~ O(n)  （時間複雜度與常係數無關）

空間複雜度：方法1爲O(n) ；   方法2爲O(1)，爲常量 26 + 1    

int firstUniqChar(string s) {
    // 方法1：數組長度123
    // int sLength = s.length();
    // int sArray[123] = {};
    // for (int i = 0; i < sLength; i++)
    // {
    // 	sArray[(int)s[i]]++;
    // }


    // for (int i = 0; i < sLength; i++)
    // {
    // 	if (sArray[(int)s[i]] == 1)
    // 	    return i;
    // }

    // return -1;

    // 方法2： 數組長度由123 -> 27:
    int len = s.length();
    int sArray[27] = {};                      // 下標爲0的元素佔位用
    // 計數：
    for (int i = 0; i < len; i++)
    {
        sArray[(int)(s[i] - 'a' + 1)] += 1;   // 數組下標從1開始，須要+1
    } 

    // 篩選：
    for (int i = 0; i < len; i++)
    {
        if (sArray[(int)(s[i] - 'a' + 1)] == 1)
            return i;
    }
    return -1;
}