剑指offer_50_第一个只出现一次的字符

第一个只出现一次的字符

题目链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/

题目内容：

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

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

限制：

0 <= s 的长度 <= 50000

题目解析

题目解析内容来自于题解中 Krahets

这题题意简单明了。立刻就能想到哈希表来统计，遍历。对应 python 中的字典。

但是在如何使用字典这件事中仍然大有可为。

方法一：哈希表

遍历字符 s，使用字典统计"各字符数量是否 > 1"。
再遍历字符串 s，在字典中找到首个"数量为 1 的字符"，并返回

算法流程：

初始化：生成一个空字典。记为 dic；
字符统计：遍历字符串 s中每一个字符 c；
1. 若 dict 中 不包含 键(key) c：则向 dic 中添加键值对(c, true)，代表字符 c 的数量为 1；
2. 若 dict 中包含键(key) c：则修改 dic 键c 的值为 false，代表字符 c 的数量 > 1；
查找数量为1的字符：遍历字符串 s 中每个字符 c; 若dic中键c对应的值为True，则返回c。
返回 " ", 代表字符串无数量为 1 的字符

复杂度分析：

时间复杂度O(N): N 为字符串 s的长度；序遍历 s两轮，使用 O(N); 字典查找的时间复杂度为 O(1)
空间复杂度O(N): 字典需存储 N 个字符的键值对，使用 O(N) 大小的额外空间

代码

Python 代码中 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 " "

方法二：有序哈希表

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

哈希表是去重的，即哈希表中键值对数量 leq≤ 字符串 s 的长度。因此，相比于方法一，方法二减少了第二轮遍历的循环次数。当字符串很长（重复字符很多）时，方法二则效率更高。

复杂度分析：

时间和空间复杂度均与 “方法一” 相同，而具体分析时间复杂度：

方法一 O(2N) ： N 为字符串 s 的长度；需遍历 s 两轮；
方法二 O(N)：遍历 s 一轮，遍历 dic 一轮。

代码

python3.6 之后，默认字典就是有序的。详情可见为什么Python 3.6以后字典有序并且效率更高？

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 " "