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

题解一:暴力
主体思路:
选定一个字母，遍历往后所有的字母，找是否出现相同的字母：
1、将所有相同的字母设置为' ',防止后续重新被遍历到。开始下一个字母；
2、遍历完所有字母都不相同，即为最后的答案；
3、所有字母都不是唯一出现则返回-1。

图示:

复杂度分析:
时间复杂度:O(n^2),双层循环;
空间复杂度:O(1),没有申请其他空间;
实现如下:

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        for(int i=0;i<str.size();++i){
            if(str[i]==' ')continue;//之前已经判断过不是唯一字符，无需判断;
            int flag=0;
            for(int j=i+1;j<str.size();++j){
                if(str[i]==str[j]){//相同
                    flag=1;//标记该字符不是唯一
                    str[j]=' ';//打上标记，防止后续重复判断
                }
            }
            if(!flag)return i;//唯一出现过的字符
        }
        return -1;//没有一个字符是唯一出现
    }
};

题解二:采用hash表存储字符出现频率
主要思路:
1、遍历数组，统计每个字符出现的频率，并存入hash表中；
2、遍历数组，并查询在hash表中出现的次数，当为1时，返回下标，遍历结束都没有找到返回-1;

图示:

复杂度分析:
时间复杂度:O(n),双次循环;
空间复杂度:O(1),字母只有26个，为常数;

实现如下:

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<char,int> u_map;
        for(auto i:str){//C++11语法
           u_map[i]++;//统计每个字符的次数
        }
        for(int i=0;i<str.size();i++){
            if(u_map[str[i]]==1)return i;//找到字符出现次数唯一的情况,返回下标
        }
        return -1;//没有一个字符是唯一出现
    }
};

题解三:数组
主要思路:与题解二一样，因为都是小写字母,所以使用可以数组充当hash表的作用;
复杂度分析:
时间复杂度:O(n),双次循环;
空间复杂度:O(1),char大小256，为常数;
实现如下:

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int flag[256] = { 0 };//hash表
    for (auto i : str) {
        flag[i]++;//统计每个字符的次数
    }
    for (int i = 0; i < str.size(); ++i) {
        if (flag[str[i]] == 1)return i;//找到字符出现次数唯一的情况,返回下标
    }
    return -1;//没有一个字符是唯一出现
    }
};