锻练编程思维——每日一题：《剑指offer》字符流中第一个不重复的字符

ゝ一纸荒年。 2023-02-14 02:34 6阅读 0赞

# 题目描述 #

题目描述  
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。  
输出描述:

> 如果当前字符流没有存在出现一次的字符，返回\#字符。

题目给出的代码框架：

class Solution
    {
        
    public:
      //Insert one char from stringstream
        void Insert(char ch)
        {
        
             
        }
      //return the first appearence once char in current stringstream
        char FirstAppearingOnce()
        {
        
        
        }
    
    };

# 题目分析 #

*  在C++中，**map可以胜任记录一个字符串所有字符的出现次数**（如此强大的STL）。
 *  然而题目代码没给你字符串，**你自己必须定义一个**，无论是在这个类的私有成员里定义，还是直接在公有成员里定义（C风格）**。我选择私有成员定义，在公有成员里访问**。map容器我也放入了私有成员里定义。
 *  题目代码给了两个函数，**第一个函数用来给字符串充入字符并记录充入的什么字符充了这个字符多少次**（map来行使记录的事情），字符串里充入字符我用的push\_back()函数，简单暴力。
 *  **第二个函数找出字符流（串）中第一个不重复的字符**，最简单好想的办法是 遍历字符串，字符串所对应的map容器里判断遍历到的字符的记录（充入字符串的次数），如果等于1，则返回该字符（遍历到的字符）
 *  **不需要异常处理**，为什么呢，如果遍历一顿后（即for循环正常结束后）也没找到第一个只充入1次的字符，就返回\#（输出描述中写到如果当前字符流没有存在出现一次的字符，返回\#字符。），字符串长度为0，也是for循环正常结束（一次没走for循环），然后返回\#就可以了。  
    也就是说把异常处理和遍历结束未找到第一个只充入1次的字符的情况合二为一，**减少空间复杂度和时间复杂度（虽然微乎其微），简洁代码**
 *  思路就这么多，代码如下

# 题解代码 #

class Solution
    {
        
    public:
      //Insert one char from stringstream
        
        
        void Insert(char ch)
        //给字符串充字符，同时用map容器记录充入什么字符，该字符的充入次数
        {
        
            str.push_back(ch);//泛型算法的东西，push_back()函数用来尾插元素
            index[ch]++;//使用map容器可以像数组一样，但是有限制，不可以真跟数组混为一谈。
        }
      //return the first appearence once char in current stringstream
        char FirstAppearingOnce()
        //该函数是找出找出字符流（串）中第一个不重复的字符
        {
        
            int n=str.size();
            //取字符串长度，作为下方for循环遍历的第二个表达式的一部分（其实直接i<str.size()也可，
            //但是这是拿unsigned int和int比较，我的codeblocks会给出警告，不知道别的IDE会怎么说）
            for(int i=0;i<n;i++)
            {
        
                if(index[str[i]]==1)
                //如果遍历到某个字符只充入字符串一次，就直接
                //return这个字符，也终止该函数运行，达到要求目的。
                {
        
                    return str[i];
                }
            }
            //异常处理和未找到只充入字符串一次的字符的情况合二为一，都返回'#'这个字符即可。
            return '#';
        }
    private:
    //类私有成员的定义，字符串和用来记录什么字符充入字符串充入几次的map容器
    //放到public:里定义也无妨（注意在第一个函数（Insert函数）外定义）。一样的。
        string str;
        map<char,int>index;
    };