剑指offer 字符流中第一个不重复的字符

Posted on |

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

题目

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

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

方法

为了高效的解决这个问题，需要在O(1)时间内王数据容器里插入一个字符，以及更新一个字符对应的值。受第一个只出现一次的字符启发，采用哈希表来实现。

  • 当哈希表中相应字符的值为1：该字符只出现1次
  • 当哈希表中相应字符的值为2：该字符至少出现2次

哈希表是没有顺序的，所以还需要一个额外的栈，数组或者队列来记录字符的顺序。基于队列先进先出的性质，符合题目中“第一个”字符。所以采用哈希表和队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# -*- coding:utf-8 -*-
class Solution:
    # 返回对应char
    def __init__(self):
        self.adict={}
        self.alist=[]
    def FirstAppearingOnce(self):
        # write code here
        while len(self.alist)>0 and self.adict[self.alist[0]]==2:
            self.alist.pop(0)
        if len(self.alist)==0:
            return '#'
        return self.alist[0]
    def Insert(self, char):
        # write code here
        if char not in self.adict:
            self.adict[char]=1
            self.alist.append(char)
        else:
            self.adict[char]=2