first-unique-character-in-a-string

First Unique Character in a String – LeetCode 387

Problem

Description

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

Example

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.

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

Answer

Original

Code

class Solution {
public:
    int firstUniqChar(string s) {
        int map[26] = {0}, pos = 0;
        char m[26] = {0};
        for(char &c: s)
            if(!(map[c - 'a']++)) m[pos++] = c;
        for(int i = 0; i != pos; ++i){
            char c = m[i];
            if(map[c - 'a'] == 1)
                for(unsigned i = 0; i != s.size(); ++i)
                    if(s[i] == c)
                        return i;
        }
        return -1;
    }
};

思路

简单的使用两个数组完成信息存储然后遍历检查即可。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$42$ ms，排名$27.68\%$

Better

思路

一样的，但是在信息存储的时候有所简化。
耗时$38$ ms，排名$8.52\%$

Code

class Solution {
public:
    int firstUniqChar(string s) {
        int map[26] = {0}, min = 0x7fffffff;
        for(unsigned i = 0; i != s.size(); ++i)
            if(!map[s[i] - 'a']) map[s[i] - 'a'] = i + 1;
            else map[s[i] - 'a'] = -1;
        for(int &i : map)
            if(i > 0 && i < min) min = i;
        return min == 0x7fffffff ?  -1 : min - 1;
    }
};