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

本文为剑指 offer 系列第三十三篇。
主要知识点为字符串，用map记录每个字符的位置和重复情况，比较简单。

题目描述

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

解题思路

构造一个map,保存每个字符第一次出现的位置。因为字符串长度不超过10000，所以每次重复出现就给保存的值加10000，这样小于10000的值就对应只出现一次的字符。
最后遍历map找最小的位置；如果最小值也不小于10000，就说明没有只出现一次的字符，返回-1。

另一种写法是用map统计出现次数，再按原字符串的顺序查找第一个只出现一次的字符。

解题代码

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.size() == 0) return -1;
        unordered_map<char,int> mmap;
        for(int i = 0;i<str.size();i++){
            if(mmap.count(str[i])){
               mmap[str[i]] += 10000;
            }else{
               mmap[str[i]] = i;
            }
        }
        int res = INT_MAX;
        for(auto a:mmap){
            res = res>a.second?a.second:res;
        }
        return res < 10000 ? res : -1;
    }
};

时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！