描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
后台会用以下方式调用Insert 和 FirstAppearingOnce 函数
string caseout = "";
1.读入测试用例字符串casein
2.如果对应语言有Init()函数的话，执行Init() 函数
3.循环遍历字符串里的每一个字符ch {
Insert(ch);
caseout += FirstAppearingOnce()
}
2. 输出caseout，进行比较。

返回值描述：

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


示例1

输入： 
"google"
返回值： 
"ggg#ll"

题目简述

        在集合中不断加入字符，对于新的集合，找到第一个只出现过一次的字符，若没有则返回 # 。

算法一: 哈希表+字符串

时间复杂度：O(N)

思路：

        每个字符都有与之对应的ASCII码，可直接与数组下标对应，我们用数组a统计每个字符出现的次数。
        Insert（）：每次插入一个元素都将它加入字符串中，然后将a数组加 1 。
        FirstAppearingOnce（）：从 t 开始遍历字符串，找到第一个只出现过一次的字符 ， 用 t 标记下这个位置，并返回它的字符串 。

代码: 

class Solution
{
public:
  //Insert one char from stringstream
    int a[1000]={0};
    queue<char> q;
    string s;
    int t=0;
    void Insert(char ch) {
        s+=ch;
        a[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {
        for(int i=t;i<s.size();i++){
            if(a[s[i]]==1){
                t=i;
                return s[i];
            }
        }
        return '#';
    }
};


算法二:哈希表+队列

时间复杂度：O(N)

思路:

        每个字符都有与之对应的ASCII码，可直接与数组下标对应，我们用数组a统计每个字符出现的次数。
        Insert（）：用数组a记录字符出现的次数，将未出现过的字符加入队列中，然后不断判断队首字符，是否出现过多次，若有多次则弹出队首字符，否则停止，这样保证了队首始终为只出现过一次的字符。
        FirstAppearingOnce（）：直接取队首元素即可，若队列为空，则返回#。

图解：

代码: 

class Solution
{
public:
  //Insert one char from stringstream
    int a[1000]={0};
    queue<char> q;
    int t=0;
    void Insert(char ch) {
        a[ch]++;//统计元素出现的次数
        if(a[ch]==1) q.push(ch); 
        while(!q.empty()){ //弹出出现多次的字符,保证队首始终是只出现过一次的字符
            if(a[q.front()]>1) q.pop(); 
            else break;
        }
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {
        if(!q.empty()){
            return q.front();
        }
        return '#';
    }
};