写在前面

剑指offer： 第一个只出现一次的字符

题目描述：

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

简单解法

  • 使用map存储出现的字符的下标，如果第一次出现存储下标。如果多次出现将value置为-1。最后遍历map找到存储的非-1的最小下标就是第一个只出现一次的字符。
  • 时间复杂度为O(n) 空间复杂度为O(52)为常数，如果不仅限于字母空间复杂度将达到O(n)。 
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(!str.size()) return -1;
        unordered_map<char,int> table;
        for(int i=0;i<str.size();++i) {
            table[str[i]]++;
        }
        for(int 0;i<str.size();++i)
            if(table[str[i]]==1)
                return i;
        return -1;
    }
};