题解 | #第一个只出现一次的字符#

NC31 第一个只出现一次的字符

题意分析：

找出字符串中只出现过一次，且最先出现字符的下标。

示例：google
返回：4
解释：字符l只出现了一次，且在是第一次出现，l的下标为4。

题解一（暴力）：

我们假设某个位置的字符是最后结果，与其他字符做比较，如果发现没有相同的，直接返回，有，则判断下一个

int FirstNotRepeatingChar(string str) {
        for(int i=0;i<str.size();i++){
            //假设位置i处为最后结果，与其他位置做比较
            int j = 0;
            for(;j<str.size();j++){
                if(str[i]==str[j]&&j!=i){
                    break;
                }
            }
            if(j==str.size()){
                //当遍历结束后，依然没有发现有相同元素，返回即可
                return i;
            }

        }
        return -1;
    }

题解二（哈希）：

先遍历一遍字符串，对字符串中各个字符进行统计。再遍历一遍字符串，根据统计结果看哪个字符只出现了一次，且是最早出现的。
假设字符串为google：
图片说明
代码实现如下：

int FirstNotRepeatingChar(string str) {
        unordered_map<char, int>character;
        //先统计每个字符出现的次数
        for(int i=0;i<str.size();i++){
            character[str[i]]++;
        }
        //遍历字符串，找出哪个字符出现了一次
        for(int i=0;i<str.size();i++){
            if(character[str[i]]==1){
                return i;
            }
        }
        return -1;
    }

时间复杂度： $O(n)$ ，假设unorder_map查看元素时间复杂度为 $O(1)$ ，其总时间复杂度为 $O(n)。$

空间复杂度： $O(n)$ ，unorder_map大小与字符串中字符种类有关，非确切上界为n，n为字符串长度。