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

题目：第一个只出现一次的字符

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

示例1输入："google"，返回值：4

解题方法一：首先看到题目，第一反应是采用暴力法进行破解，设置两个指针i和j，循环条件为字符的位数。使下标i不变，j自增1，判断下标j所指的值，如果发现两个值相同的话，直接结束判断，令i自增1，依次循环进行判断，即可得到最终结果。

实例解析： 以这个"google"为例，如下表所示：

参照C++代码如下所示：

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int len = str.size();
        if(len == 0)
            return -1;
        if(len == 1)
            return 0;
        for(int i = 0;i < len;i++){
            int flag = 1;//没有重复的标志位
            for(int j = 0;j < len;j++){
                if(i != j && str[i] == str[j]){
                    flag = 0;
                    break;
                }
            }
            if(flag == 1)
                return i;
        }
        return -1;
    }
};

其时间复杂度为O(N2)。

解题方法二：C++中有若干库函数可以直接调用，比如find_first_of()函数：查找在字符串中第一个与str中的某个字符匹配的字符，返回它的位置。和find_last_of函数：在字符串中查找最后一个与str中的某个字符匹配的字符，返回它的位置。可以将两个方法结合起来，设置与操作即可满足最后的运算结果。

具体实现的C++代码为：

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.length() == 0)
            return -1;
        for(int i = 0;i < str.length() - 1;i++){
            if(str.find_last_of(str[i]) == i && str.find_first_of(str[i]) == i)//从前往后和从后往前找见的位置是否一样
                return i;
        }
        return -1;
    }
};

其时间复杂度为O(N)。