题目的主要信息：

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

方法一：

采用队列。用q保存第一个不重复的字符Insert函数每输入一个字符，在mp中查找它是否存在，如果不存在的话，表示该字符是第一个输入的，存入q中，然后在mp中更新ch出现个数。FirstAppearingOnce函数首先遍历一遍队列q的头元素，如果该元素在当前字符流中只出现一次，则该字符是字符流中第一个不重复的字符；如果该元素不止出现一次，则把它从q中移除。

具体做法：

class Solution{
public:
    queue<char> q;//保存不重复字符
    unordered_map<char, int> mp;
    void Insert(char ch) {//每输入一个字符，统计它已出现的个数
          if (mp.find(ch) == mp.end()) {//如果在mp中没有找到ch，说明它是暂不重复
             q.push(ch);
         }
         mp[ch]++;//统计ch出现的个数
    }
    char FirstAppearingOnce() {
        while (!q.empty()) {
            char ch = q.front();
            if (mp[ch] == 1) {//如果只出现一次
                return ch;
            }else {//出现了多次，从q中移除
                q.pop();
            }
        }
        return '#';
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况下，需要遍历一整遍队列才能找到不重复字符。
空间复杂度： $O (1)$ ，mp最大为26，是常数级别。

方法二：

Insert函数每输入一个字符，在mp中更新它出现的个数，同时把该字符加到str中。FirstAppearingOnce函数中遍历一遍字符串，找到第一个不重复的字符。 alt 具体做法：

class Solution{
public:
    string str;//保存字符流
    unordered_map<char, int> mp;
    void Insert(char ch) {//每输入一个字符，统计它已出现的个数
         mp[ch]++;//统计ch出现的个数
        str += ch;
    }
    char FirstAppearingOnce() {
        for(int i = 0; i < str.size(); i++){//遍历一遍字符串
            if(mp[str[i]] == 1){//输出第一个不重复字符
                return str[i];
            }
        }
        return '#';//没有不重复字符
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，需要遍历一遍字符串。
空间复杂度： $O (n)$ ，str的大小为n。

题解 | #字符流中第一个不重复的字符#

题目的主要信息：

方法一：

方法二：