【剑指Offer】面试题35：第一个只出现一次的字符

一：题目描述

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

二：解题思路

（1）遍历字符串

创建一个数组，保存a-z  A-Z出现的次数：

1.没有出现过-1

2.只出现过一次，保存在字符串中的位置

3.出现超过一次，保存-2

（二）遍历数组

找到不为-1，同时不为-2的最小的值，即第一次只出现一次的字符

如果不存在这样的字符，返回-1

三：代码实现

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        //result用来表示a-z （0-25）  A-Z （26-51）
        //如果一个字符没有出现过-1表示，出现次数超过1次，则用-2表示，如果只出现一次，则result[i]代表第一次出现的位置
        vector<int> result(52,-1);

        int i;
        //第一次遍历字符串，统计各个字符出现的次数，位置
        for(i=0;i<str.size();i++){
             //result只有三种可能的取值，-1：该字母没有出现过  -2：该字母出现次数超过1次  i:该字母只出现过一次，i代表其出现的位置
            if(str[i]>='a' && str[i]<='z'){               
                 if(result[str[i]-'a']==-1)
                    result[str[i]-'a']=i;//如果只出现一次，记录位置
                 else
                     result[str[i]-'a']=-2;//如果出现超过一次，记为-2
            }
            else{
                if(result[str[i]-'A'+26]==-1)
                    result[str[i]-'A'+26]=i;//如果只出现一次，记录位置
                 else
                     result[str[i]-'A'+26]=-2;//如果出现超过一次，记为-2
            }

        }
        //遍历result,找到不为-1，-2，且i值最小
        bool isFind=false;
        int firstChar=INT_MAX;
        for(i=0;i<result.size();i++){
            if(result[i]!=-1 && result[i]!=-2){
                if(!isFind)
                    isFind=true;
                if(result[i]<firstChar)
                    firstChar=result[i];
            }
        }
        if(isFind)
            return firstChar;
        else
            return -1;
}
};