题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。

例如，当从字符流中只读出前两个字符 go 时，第一个只出现一次的字符是 g。

当从该字符流中读出前六个字符 google 时，第一个只出现一次的字符是 l。

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

样例

输入："google"

输出："ggg#ll"

解释：每当字符流读入一个字符，就进行一次判断并输出当前的第一个只出现一次的字符。

算法

(字符串，哈希表，队列) $O(n)$

哈希表存储字符流中每个字符出现的次数，队列中存储当前字符流中出现一次的所有字符

插入字符操作：如果当前字符 ch 出现次数大于 1，判断哈希表中添加了 ch 之后队头元素是否出现超过 1 次，如果超过 1 次就弹出队头，直到队列为空或队头元素只出现一次

获得字符串流中第一个只出现一次的字符操作：如果队列不为空则返回队头，否则返回 $#$

时间复杂度

每次插入操作平均是 $O(1)$ 的，求第一个只出现一次的字符只需要返回队头即可，也是 $O(1)$ 的，所以总共 $n$ 次操作，总时间复杂度就是 $O(n)$ 的。

C++ 代码

class Solution{
public:
    unordered_map<char, int> hash;
    queue<char> q;

    //Insert one char from stringstream
    void insert(char ch){
        if ( ++ hash[ch] > 1)
        {
            while (q.size() && hash[q.front()] > 1) q.pop();
        }
        else q.push(ch);
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        if (!q.size()) return '#';
        return q.front();
    }
};