剑指offer JZ54 字符流中第一个不重复的字符 Python 多解

一.问题描述

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

二.解题思路

这道题如果是要O(n)解法，就十分简单，我们在这就不探讨了，在这主要介绍两个O(1)时间复杂度的解法。

1.

时间复杂度: O(1),空间复杂度: O(n)

用一个集合来保存所有曾经出现过的字符，用一个OrderedDict(也可以自己实现链表)来按顺序记录在当前输入流下，只出现过一次的字符。

对于每次Insert，首先判断这个字符在不在集合中（当然也可以用256大小的数组来表示），在，说明这个字符是第二次出现，从OrderdDIct中删去。不在集合中说明是第一次出现，加入OrderedDict中去。

最后判断的时候返回OrderedDict中的第一个元素即可，若OrderedDict为空则返回'#'.

2.与上述类似，也是用一个字典来记录所有曾经出现过的字符以及它的出现次数。

但是与之不同的是，我们用一个队列来按顺序记录所有仅出现一次的字符，并且只保证这个队列的第一个元素是一定只出现过一次。

对于Insert操作，每进来一个字符，首先我们判断这个元素是否出现过，从没出现过，入队，返回现在的队列头。

如果已出现过，判断目前队列头是不是这个已出现的元素，不是的话，返回队列头，是的话，更新队列，不断出队直到队列满足队列头的字符是第一次出现。

问题1:为什么队列重的元素不是都只出现一次，而只是队列头只出现一次？

因为在Insert操作中，我们不是每出现一个重复元素，就去队列中把它删除，而是只有在该重复元素是队列头的时候才删除。

这样子队列头后面的元素就有可能是重复元素。

问题2:为什么要这样子保存队列，为什么是O(1)

这里引用来自牛客网的一篇题解中的内容：

链接：https://www.nowcoder.com/questionTerminal/00de97733b8e4f97a3fb5c680ee10720?answerType=1&f=discussion
来源：牛客网
 

复杂度计算：
从上面的描述来看，好像存在一个循环，队列的长度好像无边无际，就给人一种O(n)的感觉，其实，并不是，有如下结论：

1. 通过分析可以发现，循环（出队）的最大次数其实就是队列的长度，而队列的长度最大为128；
2. 并且随着时间的推移，队列长度 总体 先增大，后减小，正常条件下，最终队列会为空（因为随着字符流的增大，重复的字符会越来越多，队列就会不断地移除元素而越来越短）；
3. 更愉快的是，如果队列长度不减小，则循环就只执行一次，返回速度快，如果队列长度减小了，那么，循环次数上限也就减小了；

所以时间、空间复杂度是一致的，都是常数级，可是这是为什么呢，分析如下：

1. 字符的重复判断，因为使用的是直接 Hash，而且功能是计数，没有冲突，所以是O(1)；
2. 只有不重复的字符才入队列，但是不重复的字符有几个呢？ASCII字符最多也就128个，那么同一字符会不会多次入队呢？ 不会的，见3；
3. 只有队头元素变得重复了才执行循环，所以执行循环就意味着队列长度要变小。要注意，根据题意，字符的出现次数只增不减！！！所以，出队的字符不会再入队，队列长度总体上只会越来越小（或者上升到峰值就不再上升了，128种字符用尽）。

三.源码

# 1
import collections
class Solution:
    # 返回对应char
    def __init__(self):
        self.d=collections.OrderedDict()
        self.flag=set()
     
    def FirstAppearingOnce(self):
        # write code here
        for k,v in self.d.items():
            return k
        return '#'
         
    def Insert(self, char):
        # write code here
        if char in self.flag:
            if char in self.d:self.d.pop(char)
        else:
            self.flag.add(char)
            self.d[char]=0

# 2
import collections
class Solution:
    # 返回对应char
    def __init__(self):
        self.flag=[0]*256
        self.q=collections.deque()
    
    def FirstAppearingOnce(self):
        # write code here
        while(self.q):
            if self.flag[ord(self.q[0])]>1:
                self.q.popleft()
            else:return self.q[0]
        return '#'
        
    def Insert(self, char):
        # write code here
        self.flag[ord(char)]+=1
        if self.flag[ord(char)]==1:self.q.append(char)

 

本文地址：https://blog.csdn.net/CSerwangjun/article/details/107331917