本文主要是介绍剑指 Offer 50. 第一个只出现一次的字符（python3编写），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

• 1、题目描述：
• 2、方法一：暴力法
• • 思路：
  • 代码：
• 3、方法二：使用哈希表存储频数
• • 思路：
  • 代码 ：
• 4、方法三：队列+哈希表
• • 思路：（力扣官方思路）
  • 代码：

1、题目描述：

2、方法一：暴力法

思路：

最简单的想法就是：把每一个字符都与其他的字符做对比，要是对比完都没有相等的，那就直接返回这个字符即可。要是按这样的方法都没有返回，那就说明没找到，返回空格即可。

代码：

细节都在代码中。。。。。。

class Solution:
    def firstUniqChar(self, s: str) -> str:
        if s == None: return ' '
        for i in range(len(s)):
            found = True # 是否只有一个的标志
            for j in range(len(s)):
                if i != j and s[i] == s[j]: # 有重复的，把标志置位False
                    found = False
                    break
            if found:
                return s[i]
        return ' ' # 都没找到，返回空格

时间复杂度为 O ( n 2 ) O(n^2) O(n2)，空间复杂度为 O ( 1 ) O(1) O(1).

3、方法二：使用哈希表存储频数

思路：

我们可以对字符串进行两次遍历。
在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。
在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回该字符，否则在遍历结束后返回空格。

代码 ：

class Solution:
    def firstUniqChar(self, s: str) -> str:
        if s == None: return ' '
        hash_table = {}
        # 1.第一次遍历s存储到哈希表中
        for i in range(len(s)):
            try:
                hash_table[s[i]] += 1
            except:
                hash_table[s[i]] = 1
        
        # 2.第二次遍历s寻找哈希表value为1的key
        for i in range(len(s)):
            if hash_table[s[i]] == 1:
                return s[i]
        
        return ' '

时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( ∣ Σ ∣ ) O(|Σ|) O(∣Σ∣),其中 Σ Σ Σ 是字符集，在本题中 s s s 只包含小写字母，因此 ∣ Σ ∣ ≤ 26 ∣Σ∣≤26 ∣Σ∣≤26.

4、方法三：队列+哈希表

思路：（力扣官方思路）

我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。

具体地，我们使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。当我们对字符串进行遍历时，设当前遍历到的字符为 c c c，如果 c c c 不在哈希映射中，我们就将 c c c 与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 − 1 -1 −1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。

在遍历完成后，如果队列为空，说明没有不重复的字符，返回空格，否则队首的元素即为第一个不重复的字符以及其索引的二元组。

注意：

在维护队列时，我们使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，我们也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，我们才需要将它移除。

代码：

class Solution:
    def firstUniqChar(self, s: str) -> str:
        position = dict() # 哈希表
        q = collections.deque() # 队列
        n = len(s)
        for i, ch in enumerate(s):
            if ch not in position: # 不在哈希表中，则保存到哈希表中，且入队
                position[ch] = i # 哈希表的value为第一次出现字符的下标
                q.append((s[i], i))
            else:
                position[ch] = -1 # 重复出现了，则把value设置为-1
                while q and position[q[0][0]] == -1: # 队首元素重复出现，则出队
                    q.popleft()
        return ' ' if not q else q[0][0]

这篇关于剑指 Offer 50. 第一个只出现一次的字符（python3编写）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！