题目的主要信息：

• 实现一个函数用来找出字符流中第一个只出现一次的字符
• Insert函数插入字符流的下一个字符， FirstAppearingOnce找到第一个不重复出现的字符
• 如果找不到返回#
• 字符串中出现的字符一定在 ASCII 码内
• 进阶要求：时间复杂度：$O(n)O(n)$，空间复杂度：$O(n)O(n)$

方法一：哈希表+字符串

具体做法：

可以准备一个字符串string来记录输入的字符流，用哈希表unordered_map统计每个字符的次数，二者都是全局变量。

在Insert函数中对输入的字符，加到字符串最后，然后统计出现次数。

在FirstAppearingOnce函数遍历该字符串，对于每个字符查找哈希表，返回第一个计数为1的字符，如果遍历完字符串以后都没，则返回#。

class Solution
{
public:
    unordered_map<char, int> mp;
    string s;
  //Insert one char from stringstream
    void Insert(char ch) {
        s += ch;  //插入字符
        mp[ch]++; //哈希表记录字符出现次数
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {
        for(int i = 0; i < s.length(); i++) //遍历字符串
            if(mp[s[i]] == 1) //找到第一个出现次数为1的
                return s[i];
        return '#'; //没有找到
    }

};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，每次插入字符都是$O(1)O(1)$，每次查询需要遍历字符串$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，字符一定在ASCⅡ范围内，因此哈希表大小为常数，但是记录的字符串长度为还是为$nn$

方法二：哈希表+队列

具体做法：

除了使用字符串记录字符流，还可以用队列记录字符流，每次插入的时候，只需要将第一次出现的字符加入到队列中，然后正常计数。

查找第一个不重复出现的字符的时候，从队首开始查询哈希表，如果出现次数为1，则返回该字符，如果不为1，则从队首将其弹出，因为反正后续也不可能是这个已经重复的字符了。

如果最后队列为空，则返回#，说明之前的字符都已经重复了。

class Solution
{
public:
    unordered_map<char, int> mp;
    queue<char> q;
  //Insert one char from stringstream
    void Insert(char ch) {
        if(mp.find(ch) == mp.end()) //第一次出现加入队列中
            q.push(ch);
        mp[ch]++; //哈希表记录字符出现次数
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {
        while(!q.empty()){
            if(mp[q.front()] == 1) //第一个不重复的字符
                return q.front();
            else //弹出前面的已经重复的字符
                q.pop();
        }
        return '#'; //都重复了
    }

};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，每次插入字符都是$O(1)O(1)$，每次查询平均复杂度比方法一下降了，但是最坏需要遍历队列$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，字符一定在ASCⅡ范围内，因此哈希表大小为常数，同时记录字符的队列也是常数