题目描述

在字符串中找出第一个只出现一次的字符。
如输入”abaccdeff”，则输出b。
如果字符串中不存在只出现一次的字符，返回 # 字符。

样例

输入：”abaccdeff”
输出：’b’

时间复杂度

O(n)

C++ 代码

class Solution {
public:
    char firstNotRepeatingChar(string s) {

        int times[126]={0}; //26个字符出现的次数(可显示字符是从32到126的)
        int index[126]={-1}; //每个字符第一次出现的位置
        int n = s.length();

        /*统计每个字符出现次数，以及第一次出现时的位置*/
        for(int i = 0; i < n; i++)
        {
            int a = s[i];
            times[a]++;
            if(times[a] == 1)
            {
                index[a] = i;    
            }
        }

        int flag = 0;
        int tmpindex = -1;
        int min = 10000;

        for (int i = 0; i < n; i ++ ){
             int a = s[i];
            //找到出现次数为1的字符，然后找出它们中间最早出现的那一个
            if(times[a] == 1){ 
                flag = 1; //存在只出现一次的字符的标志
                tmpindex = index[a];
                if(tmpindex < min) min = tmpindex;
            }
        }

        if(flag == 1){
            return s[min];
        }else{
            return '#';
        }
    }
};