[Python知识库]【Python】【剑指Offer.50】第一个只出现一次的字符

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

示例:

s = “abaccdeff”
返回 “b”

s = “”
返回 " "

限制：
0 <= s 的长度 <= 50000

我比较笨，第一次想到的是

class Solution:
    def firstUniqChar(self, s: str) -> str:
        dic = {c: s.count(c) for c in s}
        for k, v in dic.items():
            if v == 1:
                return k
        return " "
# 超时了！O(n2)  s.count(c)一个O(n), for循环一个O(n)，O(n)*O(n)

改进一下，O(n) + O(n)，还是O(n)

class Solution:
    def firstUniqChar(self, s: str) -> str:
        dic = {}
        for c in s:
            dic[c] = c not in dic
        for c in s:
            if dic[c]:
                return c
        return " "
# 执行用时: 80 ms
# 内存消耗: 14.9 MB

将第二轮循环改成遍历字典，因为这里的key有字母组成，最多26遍即可遍历完成

class Solution:
    def firstUniqChar(self, s: str) -> str:
        dic = {}
        for c in s:
            dic[c] = c not in dic
        for k, v in dic.items():
            if v:
                return k
        return " "
# 执行用时: 60 ms
# 内存消耗: 14.9 MB