字符串中第一个只出现一次的字符

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode” return 0.
s = “loveleetcode”, return 2.

Note: You may assume the string contain only lowercase letters.

---

最开始的解法：

class Solution {
public:
    int firstUniqChar(string s) {
        if (s.size() == 0) {
		    return -1;
	    }

	    int* mask = new int[s.size()]{0};
	    for (int i = 0; i < s.size(); ++i) {
            if (mask[i]) {
                continue;
            }
		    for (int j = i + 1; j < s.size(); ++j) {
			    if (!mask[j] && s[i] == s[j]) {
				    mask[i] = mask[j] = 1;
			    }
		    }
	    }

	    for (int i = 0; i < s.size(); ++i) {
		    if (!mask[i]) {
			    return i;
		    }
	    }
	    return -1;
    }
};

问题在于时间复杂度高，在第一个for循环里continue的方法对时间复杂度有缓解，但是依旧效率不高。

考虑到字符的所有可能是26种情况（忽略掉大小写），那么可以遍历一次建立一个计数器，统计出只出现一次的字符，第二次遍历找出第一个出现的字符即可。

int firstUniqChar(string s) {
    int* arr = new int[26]{0};
    for(int i = 0; i < s.size();i++){
        arr[s[i] - 97] += 1;
    }
    for(int i = 0; i < s.size(); i++){
        if(arr[s[i] - 97] == 1){
            return i;
        }
    }
    return -1;
}