题目

• 请实现一个函数用来找出字符流中第一个只出现一次的字符。
• 例如，当从字符流中只读出前两个字符 go 时，第一个只出现一次的字符是 g。
• 当从该字符流中读出前六个字符 google 时，第一个只出现一次的字符是 l。
• 如果当前字符流没有存在出现一次的字符，返回 # 字符。
• 数据范围

字符流读入字符数量 [0,1000]。

示例

• 输入："google"
• 输出："ggg#ll"

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

代码

• 单调队列【视频讲解】

class Solution{
public:
    unordered_map<char,int>count;
    queue<char> q;
    //Insert one char from stringstream
    void insert(char ch){
        //当新的字符已经重复，则不插入，而且将队首有可能重复的pop出来。goo，当新来第二个O，
        //此时队首不重复的，证明O永远不会输出，所以此时O不用插入。队列里只存一个o，pop的时候，count里O是两个
        //所以O还是可以正常pop
        if(++count[ch] > 1){
            while(q.size() && count[q.front()] > 1) 
                q.pop();
        }else 
            q.push(ch);
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        if(q.empty()) return '#';
        return q.front();
    }
};

代码分析：把可能重复的字符全部pop()出去，省去了不必要的查找，代码时间复杂度$O(n)$

一般优化代码的方法：双指针思想和借助单调队列。

题目：字符流中第一个只出现一次的字符

相关题目：字符串中第一个只出现一次的字符