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

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

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

 

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

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

g

o

o

g

l

e

i指针j指针

 

 

 

 

 

第一轮判断，i指针的值与j指针的值是否相等，以及i不等于j，不符合条件，j++

g

o

o

g

l

e

i

 

j

 

 

 

i

 

 

j

 

 

相等的话，令i++，j从头开始

g

o

o

g

l

e

j

i

 

 

 

 

 

i，j

 

 

 

 

 

i

j

 

 

 

i不等于j，但是i对应的值与j对应的值相等，令i++，经过不断循环，最终得到最终结果值，最终值为下标位置为i的值

 

参照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中的某个字符匹配的字符，返回它的位置。可以将两个方法结合起来，设置与操作即可满足最后的运算结果。

g

o

o

g

l

e

0

 

 

3

 

 

 

1

2

 

 

 

 

 

 

 

4

 

具体实现的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)。