字符流中第一个不重复的字符

题目的主要信息：

• 实现一个函数用来找出字符流中第一个只出现一次的字符
• Insert函数插入字符流的下一个字符， FirstAppearingOnce找到第一个不重复出现的字符
• 如果找不到返回#
• 字符串中出现的字符一定在 ASCII 码内

举一反三：

学习完本题的思路你可以解决如下题目：

JZ50. 第一个只出现一次的字符

JZ39. 数组中出现次数超过一半的数字

JZ56. 数组中只出现一次的两个数字

方法一：哈希表+字符串（推荐使用）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

又是一个找到是否重复的问题。我们还是可以用哈希表来记录各个字符出现的次数，根据这样只要是字符串最前面且哈希表中次数为1的字符就是我们要找的。

具体做法：

• step 1：准备一个字符串来记录输入的字符流，用哈希表统计每个字符的次数，二者都是全局变量。
• step 2：在Insert函数中对输入的字符，加到字符串最后，然后统计出现次数。
• step 3：在FirstAppearingOnce函数遍历该字符串，对于每个字符查找哈希表，返回第一个计数为1的字符，如果遍历完字符串以后都没，则返回#。

Java实现代码：

import java.util.*;
public class Solution {
    private StringBuilder s = new StringBuilder();
    private HashMap<Character, Integer> mp = new HashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        //插入字符
        s.append(ch);  
        //哈希表记录字符出现次数
        mp.put(ch, mp.getOrDefault(ch, 0) + 1);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //遍历字符串
        for(int i = 0; i < s.length(); i++) 
            //找到第一个出现次数为1的
            if(mp.get(s.charAt(i)) == 1)
                return s.charAt(i);
        //没有找到
        return '#'; 
    }
}

C++实现代码：

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++) 
            //找到第一个出现次数为1的
            if(mp[s[i]] == 1) 
                return s[i];
        //没有找到
        return '#'; 
    }
};

Python实现代码：

class Solution:
    def __init__(self):
        self.s = ""
        self.mp = dict()
        
    def FirstAppearingOnce(self):
        #遍历字符串
        for c in self.s:
            #找到第一个出现次数为1的
            if self.mp[c] == 1:
                return c
        #没有找到
        return '#' 
        
    def Insert(self, char):
        #插入字符
        self.s += char  
        #哈希表记录字符出现次数
        if char in self.mp:
            self.mp[char] += 1
        else:
            self.mp[char] = 1

复杂度分析：

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

方法二：哈希表+队列（扩展思路）

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

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

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

具体做法：

• step 1：准备一个队列来记录输入的字符流，用哈希表统计每个字符的次数，二者都是全局变量。
• step 2：在Insert函数中对输入的字符，加到队列最后，然后统计出现次数。
• step 3：在FirstAppearingOnce函数中，不断检查队首元素直到队列为空，队首出现次数为1次，就返回，队首出现次数不为1就弹出。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    private Queue<Character> q = new LinkedList<>();
    private HashMap<Character, Integer> mp = new HashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        //插入字符
        if(!mp.containsKey(ch))
            q.offer(ch);
        //哈希表记录字符出现次数
        mp.put(ch, mp.getOrDefault(ch, 0) + 1);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        while(!q.isEmpty()){
            //第一个不重复的字符
            if(mp.get(q.peek()) == 1) 
                return q.peek();
            //弹出前面的已经重复的字符
            else 
                q.poll();
        }
        //都重复了
        return '#'; 
    }
}

C++实现代码：

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 '#'; 
    }
};

Python实现代码：

class Solution:
    def __init__(self):
        self.q = []
        self.mp = dict()
        
    def FirstAppearingOnce(self):
        while len(self.q) != 0:
            #第一个不重复的字符
            if self.mp[self.q[0]] == 1: 
                return self.q[0]
            #弹出前面的已经重复的字符
            else:
                self.q.pop(0)
        #都重复了
        return '#' 
        
    def Insert(self, char):
        #哈希表记录字符出现次数
        if char in self.mp:
            self.mp[char] += 1
        else:
            self.mp[char] = 1
            #插入字符
            self.q.append(char)

复杂度分析：

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