跟着姚桑学算法-字符流中第一个只出现一次的字符

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

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

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

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

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

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

样例

输入："google"

输出："ggg#ll"

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

【题解】--- 简单映射

利用chars 存储用set过滤出现过的字符次序；
cn 记录每个字符的出现次数，字符通过映射getI找到下标；
每次查询chars中字符的times，第一个出现1的字符返回即可。

复杂度分析：

时间复杂度为 O(n)。

C++代码实现：

// 常规思路
class Solution{
public:
    unordered_map<char,int> cnt;
    queue<char> q;
    //Insert one char from stringstream
    void insert(char ch){
        //最先出现的字符必然先插入的字符，故而我们可以考虑使用双指针，一个指针指向最开头元素,
        //另外一个指向当前插入的字符，可以采用队列的数据结构。
        //具体步骤如下，将当前插入的字符与队头字符cnt比较，如果当前字符已出现过，弹出队头，处理
        //下一个元素，时间复杂度为On
        if(++cnt[ch] > 1){
            while(q.size() && cnt[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();
    }
};

// 简单映射法
class Solution{
public:
    static const int n=1010;

    char chars[n];
    int cn[11010];
    int now=0;
    set<char> setc;

    int getI(char c){
        return 10000+(int)c;
    }

    //Insert one char from stringstream
    void insert(char ch){
        //count times
        int idx=getI(ch);
        cn[idx]++;
        //次序
        if(setc.count(ch)==0){
            chars[now]=ch;
            now++;
        }
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        for(int i=0;i<now;i++){
            char c=chars[i];
            int idx=getI(c);
            int times=cn[idx];
            if(times==1){
                return c;
            }
        }
        return '#';
    }
};