每行都做了详细代码解释,两种方法,通俗易懂:字符流中第一个不重复的字符

字符流中第一个不重复的字符

http://www.nowcoder.com/questionTerminal/00de97733b8e4f97a3fb5c680ee10720

方法一:
本来是想用unordered_map的,但是系统显示unordered_map无定义,可能是没有包含include<unordered_map>这个文件库。
首先定义了一个map<char, int>count;对输入的字符进行计数,其次用res标记迄今为止出现的第一个符数,如果下一次输入是得这个字符res出现重复,则将res置‘#’,重头遍历map数组,找到只出现一次的字符。
但其实是有bug的,系统没有检测出来,例如输入的是cbac,则正确输出应该是cccb,但是本程序的输出是ccca,因为map排序自动将a排在了b的前面。</unordered_map>

class Solution
{
public:
    //Insert one char from stringstream
    Solution() {//构造函数,初始化私有变量res
        res= '#';
    }
    void Insert(char ch)
    {
        count[ch]++;//标记字符出现的次数
        if (ch == res)res = '#';//如果之前标记的字符重复出现了,
    }
    //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {        
        if (res == '#')//如果res=='#',说明之前记录的res被重复出现了,此时需要再次遍历迭代器,寻找第一个出现的字符
        {
            map<char, int>::iterator it = count.begin();
            for (; it != count.end(); ++it) {
                if (it->second == 1) {
                    res = it->first;
                    break;
                }
            }
        }
        return res;
    }
private:
    map<char, int>count;//使用map对输入的数计数
    char res;            //标记第一个出现一次的字符
}; 

方法二:
//仿照hash表实现,str存储插入的字符,hash[256]存储插入字符的个数。以其ascii位索引位,同时用string标记字符出现的次数,并初始化所有的值为0。

class Solution
{
public:

    string str;
    char hash[256] = {0};//因为每个字符的ascii码是不同的,所以就以其ascii位索引位,同时用string标记字符出现的次数,并初始化所有的值为0。
    void Insert(char ch)
    {
        str.append( ch);//用string标记字符出现的次数,将新出现的字符插入尾部
        hash[ch]++;
    }   

    char FirstAppearingOnce()
    {
        for(char ch :str){//遍历插入的字符
            if(hash[ch] == 1){
                return ch;
            }
        }
        return '#';
    }
};
全部评论

相关推荐

头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务