面试题50(1):第一次只出现一次的字符

题目

字符串中第一次只出现一次的字符
例如:在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出‘b’

解题思路

统计每个字符出现的次数就好了。
1)用容器存放每个字符出现的次数，即可以将一个字符映射称一个数字。拥有哈希表的容器非map不可

2. 构建一个类似哈希表的数组
3. 注意字符是一个长度为8的数据类型，共有256种可能。故应创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的一个数字。

代码

代码中传递的参数是字符串类型的形参s，而书中的参数是char型的形参s，故需要加*,取首元素地址。

• map方式

class Solution{
    public:
        char FirstNotRepeating(string s)
        {
            
            map<char,int> mp;
            for(int i = 0;i<s.size();i++)
            {
                mp[s[i]]++;
            }
            for(int i = 0;i<s.size();i++)
            {
                if(mp[s[i]] == 1)
                {
                    return s[i];
                }
            }
            return -1;
        }
}

• 简易的哈希表数组

class Solution{
    public:
        char FirstNotRepeatingChar(string s)
        {
            int len = s.size();
            int *mp = new int[256];
            for(int i=0;i<len;i++)
            {
                mp[s[i]]++;
            }
            for(int i=0;i<len;i++)
            {
                if(mp[s[i]] == 1)
                {
                    return s[i];
                }
            }
            return -1;
        }
};

完整代码见GitHub