剑指offer 第一个只出现一次的字符

太过爱你忘了你带给我的痛 2022-05-21 05:19 124阅读 0赞

# 题目描述 #

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

# 解题思路 #

我们遍历这个字符串，假设每个当前字符都是只出现一次的，我们分别向前和向后考察是否存在相同字符  
向前考察：保存一个vector里面存放所有已知的已经重复过的字符，如果当前字符跟这个vector里面的字符相同，那必然不是只出现一次的  
向后考察：遍历当前字符后面的字符，如果出现跟当前字符相同的，立即停止，将当前字符加入vector中，接着work on下一个字符  
向前和向后考察都通过了，立即return 该字符的位置，算法结束

# 代码 #

#include<vector>
    class Solution {
    public:
        bool repeat_before(vector<char> repeatarr,char curr){
            for(vector<char>::iterator itera=repeatarr.begin();itera!=repeatarr.end();itera++){
                    if(curr==*itera){
                        return true;
                    }
                }
            return false;
        }
        int FirstNotRepeatingChar(string str) {
            char curr;
            int result;
            int length=str.size();
            vector<char> notunique;
            //对字符串的每一个进行考察
            for(int i=0;i<length-1;i++){
                curr=str.at(i);//假设当前该字符是只出现一次的字符
                //如果该字符跟之前的字符重复，跳过
                if(repeat_before(notunique,curr)) continue;
                bool isunique=true;
                result=i;
                //判断之后的
                for(int j=i+1;j<length;j++){
                    if(str.at(j)==curr){
                        isunique=false;
                        result=i+1;
                        notunique.push_back(curr);
                        break;
                    }
                }
                if(isunique){
                    return result;
                }
            }
            return -1;
        }
    };