题目的主要信息:
  • 实现一个函数用来找出字符流中第一个只出现一次的字符
  • 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就弹出。

图示:

alt

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Ⅱ范围内,因此哈希表大小为常数,同时记录字符的队列也是常数