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

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符"google"时，第一个只出现一次的字符是"l"。

解题思路

核心思想：使用哈希表记录每个字符出现的次数和位置。

。

关键步骤：

1. 使用字典记录字符计数
2. 使用列表记录字符顺序
3. 找到第一个计数为1的字符

时间复杂度：插入O(1)，查询O(n) 空间复杂度：O(1)（字符集有限）

Python 实现

class FirstNotRepeatingChar:
    def __init__(self):
        self.char_count = {}
        self.char_order = []

    def insert(self, char):
        """
        插入字符

        Args:
            char: 插入的字符
        """
        if char in self.char_count:
            self.char_count[char] += 1
        else:
            self.char_count[char] = 1
            self.char_order.append(char)

    def first_appearing_once(self):
        """
        获取第一个只出现一次的字符
        """
        for char in self.char_order:
            if self.char_count[char] == 1:
                return char
        return '#'


# 测试代码
if __name__ == "__main__":
    fnrc = FirstNotRepeatingChar()

    test_str = "google"
    for char in test_str:
        fnrc.insert(char)
        result = fnrc.first_appearing_once()
        print(f"插入'{char}'后，第一个不重复: '{result}'")

# 输出:
# 插入'g'后，第一个不重复: 'g'
# 插入'o'后，第一个不重复: 'g'
# 插入'o'后，第一个不重复: 'g'
# 插入'g'后，第一个不重复: 'l'
# 插入'l'后，第一个不重复: 'l'
# 插入'e'后，第一个不重复: 'l'