字符串中的第一个唯一字符(First Unique Character in a String)

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

示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

提示： 你可以假定该字符串只包含小写字母。

int firstUniqChar(char * s){
    int sSize = strlen(s);

    for (int i = 0; i < sSize; i++){
        if (s[i] == '-') continue;

        bool isUnique = true;
        for(int j =i+1; j<sSize; j++){
            if (s[j] == s[i]){
                isUnique = false;
                s[j] = '-';
            }
        }
        if (isUnique){
            return i;
        }
    }
    return -1;
}

这种时间复杂度为O(n^2)

或者

int firstUniqChar(char * s){
    int sSize = strlen(s);

    for (int i = 0; i < sSize; i++){
        bool isUnique = true;
        for(int j =0; j<sSize; j++){
            if (s[j] == s[i] && i!=j){
                isUnique = false;
                break;
            }
        }
        if (isUnique){
            return i;
        }
    }
    return -1;
}

两种做法基本类似

接下来是我们耳熟能详的空间换时间的时间

int firstUniqChar(char * s){
    int sSize = strlen(s);

    int count[26] = {0};
    for (int i = 0; i < sSize; i++){
        if (count[s[i]-'a']>1) continue;
        count[s[i]-'a']++;
    }
    for (int i = 0; i < sSize; i++){
        if (count[s[i]-'a'] == 1) return i;
    }
    return -1;
}

这时候的时间复杂度就变成了 O(n)