剑指 Offer 50. 第一个只出现一次的字符（Python3解法）

1：问题描述

来源：LeetCode

难度：简单

---

问题详情：
  在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格‘ ‘。 s 只包含小写字母。

示例 1:

输入：s = “abaccdeff”
输出：‘b’

示例 2:

输入：s = “”
输出：’ ’

限制：

0 <= s 的长度 <= 50000

---

2：问题分析

2.1 时间复杂度和空间复杂度

  在真正开始介绍各种算法前，先以表格形式展示各自的时间复杂度和空间复杂度，其中$n$表示字符串$s$的长度。

2.2 暴力法

  使用字典统计每个字符的出现频次，因为目前较新的python3版本中的字典其实已经是有序字典，所以不用担心key值出现顺序混乱的问题。

2.2.1 代码

def firstUniqChar(s: str) -> str:
    value_dict = {}
    for item in s:
       value_dict[item] = value_dict.get(item, 0) + 1
    
    for key,value in value_dict.items():
        if value == 1:
            return key
    
    return ' '
1
2
3
4
5
6
7
8
9
10

  时间复杂度为$O(n)$,空间复杂度最坏为$O(n)$，即每个字符只出现一次的情况。

2.3 队列法

2.3.1 方法解释

   我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。
   该方法同样使用字典，但是其是用来辅助队列进行出队操作。

流程如下：

1. 字典用来存储{字符：出现的索引或者-1}，-1表示该字符已经出现超过一次
2. 队列按顺序存储每个不重复的字符
3. 遍历每个字符，如果字符还未添加至字典，那么就添加{字符：出现的索引}，同时将该字符入队。
4. 如果该字符已经在字典中，那么就更新{字符：-1}，然后去判断队首元素中的字符对应的字典中的value是否为-1，即查看队首元素中的字符是否已经出现过，如果出现则弹出；然后循环判断队首字符是否已经出现过，直至不满足条件或者队列为空。
5. 当遍历结束后，返回队首元素中的字符；如果队列为空，返回’ ‘

   其中第4步的原因，我们只关心第一个只出现一次的字符，则如果队首元素（先进入的元素）还未发现重复，我们就一直关注队首元素。直至发现重复，我们才会选择弹出队首元素，然后关注新队首元素。前面的字符没有丧失成为第一个只出现一次的字符的的权利的情况下，我们就不会考虑后面的字符。

   以s='abbac'为例：

• 当遍历到第2个b时，字典中的元素是{’a‘:0,'b':-1},队列元素是{’a‘,'b'},然后我们发现队首元素'a'在字典中的元素不为-1，也就是没有重复，那么我们就重点关注’a‘，所以这一步我们不弹出任何元素，即使’b‘已经第二次出现。
• 遍历到第2个’a‘时，我们就弹出队列中’a‘，所以队列变为{'b'},再次判断发现新队首’b‘也出现超过1次了，再次弹出，所以变为了空队列；
• 遍历到’c‘,添加至字典，入队，返回‘c’

2.3.2 代码

def firstUniqChar(self, s: str) -> str:
    position = dict()
    q = collections.deque()
    for i, ch in enumerate(s):
        if ch not in position:
            position[ch] = i
            q.append(ch)
        else:
            position[ch] = -1
            while q and position[q[0]] == -1:
                q.popleft()
    return ' ' if not q else q[0]
1
2
3
4
5
6
7
8
9
10
11
12

  时间复杂度为$O(n)$,空间复杂度最坏为$O(n)$，即每个字符只出现一次的情况。