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

题目描述

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

思路及Python实现

思路一：用一个字典和队列来完成

class Solution:
    # 注意，是第一次出现的不重复的字符，不是出现一个不重复的就返回一个
    # 返回对应char
    def __init__(self):  # 设置一个字典，用来记录每个字符出现的次数
        self.memory = dict()
        # 设置一个队列用来记录字符流的出现的顺序，元素入队的时候，相同元素只入一次队
        # 根据字典记录的元素出现的次数来判断元素是否出队。
        self.queue = []

    def FirstAppearingOnce(self):
    	# 循环，队列排在前面的一定是先出现的，因此，要删除出现多次的队首元素，直到遇见只出现一次的字符，返回
        while len(self.queue) and self.memory[self.queue[0]] > 1:
            self.queue.pop(0)
        return self.queue[0] if len(self.queue) else '#'

    def Insert(self, char):
        if char not in self.memory:
            self.memory[char] = 0
        self.memory[char] += 1
        if self.memory[char] == 1:
            # 如果不等于1，说明前面已经出现过了，再次入队会造成重复，降低效率。
            self.queue.append(char)
            
obj = Solution()
s = input("请输入字符:")
for e in s:
    obj.Insert(e)
print(obj.FirstAppearingOnce()) # >>google >>> l

思路二：码值

由于ASCII码有128位，扩展的ASCII码有256位，字符最多有256个（不考虑中文字符），因此我们可以利用一个长度为256的数组来实现一个类似于字典的功能。
数组的各个位置（0-256）就相当于字符的ASCII码。数组的值初始化为-1， 表示第一次读入。数组的值不为-1且大于等于0时，表示不是第一次读入，修改当前的值为-2，在读入的时候，如果碰见-2，就不再进行处理了。同时要设置一个读入顺序的指标，当元素不为-2时，将这个指标赋值给不等于-2的元素。在读取的时候要读取数组元素值不大于等于0的最小的元素，并返回这个位置所代表的字符。

class Solution:
    def __init__(self):
        self.occurence = [-1 for i in range(256)]
        self.index = 0  # 记录当前字符的出现的前后顺序，index越小，出现的越早，返回的时候，都是出现一次的时候，要返回index最小的  
        # 记录当前字符的出现的前后顺序，index越小，出现的越早，返回的时候，都是出现一次的时候，要返回index最小的

    def FirstAppearingOnce(self):
        # write code here
        minValue = 10000  # 设置一个超大的数，使读入的字符流的长度小于min_value
        minIndex = -1
        for i in range(256):  # 循环遍历找到数组取值大于-1的最小值，并返回minIndex
            if self.occurence[i] >= 0:
                # 表示出现过1次，-1表示没出现过，-2表示出现过多次，只有大于-1才表示只出现过一次
                if self.occurence[i] < minValue:
                    minValue = self.occurence[i]
                    minIndex = i
        if minIndex >= 0:
            return chr(minIndex)
        else:  # 如果minIndex仍然等于-1，表示没有数组元素>=0,即要么没出现，要么出现过多次。返回“#”
            return '#'

    def Insert(self, char):
        # 如果是第一出现，则将对应元素的值改为下边
        if self.occurence[ord(char)] == -1:
            self.occurence[ord(char)] = self.index
        # 如果不是-1，表示之前出现过了，再次出现就不是第一次了，修改当前的数组元素值为-2
        else:
            self.occurence[ord(char)] = -2
        self.index += 1  # 每读入一个字符，index+1，表示前后顺序