本文共 1478 字，大约阅读时间需要 4 分钟。

【思路1】哈希表

1. 初始化： 字典 (Python)，记为 dic ；
2. 字符统计： 遍历字符串 s 中的每个字符 c ；
   • 若 dic 中 不包含 键(key) c ：则向 dic 中添加键值对 (c, True) ，代表字符 c 的数量为 1 ；
   • 若 dic 中 包含 键(key) c ：则修改键 c 的键值对为 (c, False) ，代表字符 c 的数量 > 1 。
3. 查找数量为 1 的字符：
   遍历字符串 s 中的每个字符 c ；
   若 dic中键 c 对应的值为 True ：，则返回 c 。
4. 返回 ’ ’ ，代表字符串无数量为 1 的字符。

注：

• not c in dic 整体为一个布尔值；
• c in dic 为判断字典中是否含有键 c

class Solution:    def firstUniqChar(self, s: str) -> str:        dic = {
   }        for c in s:            dic[c] = not c in dic        for c in s:            if dic[c]: return c        return ' ''''作者：jyd链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/来源：力扣（LeetCode）'''

• 时间复杂度 O(N)： N 为字符串 s 的长度；需遍历 s 两轮，使用 O(N) ；HashMap 查找操作的复杂度为 O(1)；
• 空间复杂度 O(1) ： 由于题目指出 s 只包含小写字母，因此最多有 26 个不同字符，HashMap 存储需占用 O(26) = O(1) 的额外空间。

【思路2】遍历哈希表查找字符

在哈希表的基础上，有序哈希表中的键值对是 按照插入顺序排序 的。基于此，可通过遍历有序哈希表，实现搜索首个 “数量为 1 的字符”。

哈希表是 去重 的，即哈希表中键值对数量 ≤ 字符串 s 的长度。

复杂度同上，不一样的是该法只需遍历一轮字符串s

class Solution:    def firstUniqChar(self, s: str) -> str:        dic = {
   }        for c in s:            dic[c] = not c in dic        for k, v in dic.items():            if v:             	return k        return ' ''''作者：jyd链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/来源：力扣（LeetCode）'''

比如 s=‘ababc’，第二轮遍历s 得5次才找到c

而dic={‘a’: False, ‘b’: False, ‘c’:True}，遍历dic只需3次找到

用有序表反而慢了 dic = collections.OrderedDict()

转载地址：http://dfjii.baihongyu.com/