1.常规正向思路

（首先小小吐槽一下：牛客为啥非要把简单的题目搞得很复杂。。。明明这题一个函数就可以解决的非要搞两个，但是为了遵守官方的规则，只有复杂一下(ˉ▽ˉ；)...）
我们还是先看题目描述：“
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。”，很明显这里已经告诉我们，会用到遍历这个方法以及统计字符出现次数这个信息。

接下来官方给出了两个函数，说是后台会调用，其中“Insert”函数表示👉循环遍历字符串里的每一个字符👈；
而FirstAppearingOnce函数则是用来查找第一个不重复字符的。

注意：当一个字符串全是重复字符的时候，直接返回 # 字符。

2. 算法图解

根据上面的思路，我们这里可以采用常规解法👉 字符频数统计之列表法
图片说明

3. 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.l = []
    def FirstAppearingOnce(self):
        for i in self.l:
            if self.l.count(i) == 1: #遍历统计列表字符个数，找到等于1那个就停止遍历
                return i
        return '#'                   #如果不存在=1的，就返回#
    def Insert(self, char):
        self.l += char               #循环遍历字符串里的每一个字符

4. 复杂度分析

时间复杂度：O(n) (因为存在两次遍历，所以其实是O(2n),常数可略，即为O(n));
空间复杂度：O(n)。

------------------------------------------------------我是字典的分割线----------------------------------------------------------------------

思路：

由于该题要找的是第一个不重复的字符，也可以利用字典这种数据结构来转换字符串为键值的形式，来统计每个键的次数。具体操作如下图：
图片说明

核心代码：

# -*- coding:utf-8 -*-
class Solution:
    # 返回对应char
    def __init__(self):
        self.s = ''
        self.dic = {}       #初始化字典
    def FirstAppearingOnce(self):
        # write code here
        #遍历字典的key，查找第一个键对应值为1的
        for i in self.s:
            if self.dic[i] == 1:
                return i
        return '#'
    def Insert(self, char):
        # write code here
        #遍历字符串
        self.s+=char
        #判断每个字符是否在字典中，如果在，就在字典中该键对应值+1；否则就是更新到字典中，并写入键的值为1
        if char in self.dic:
            self.dic[char]+=1
        else:
            self.dic[char]=1

复杂度分析

  • 时间复杂度：O(n) (需要遍历的字符串和字典的长度，所以为O(n)）
  • 空间复杂度：O(n) (同上)