剑指Offer[50]-第一个只出现一次的字符

题目

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

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

python代码

class Solution:
    def firstUniqChar(self, s: str) -> str:
        odrer_dict = {}
        for i in s:
            if i in odrer_dict:
                odrer_dict[i]+=1
            else:
                odrer_dict[i] = 1
        for i in odrer_dict.keys():
            if odrer_dict[i]==1:
                return i
        return " "

这道题的解题思路与剑指Offer[39]- 数组中出现次数超过一半的数字还是有相似之处的,利用额外的空间来降低时间复杂度。

  • 首先遍历一遍字符串,记录每个字符出现的次数(此时字典中key的顺序就是字符串中每个字符按首次出现的顺序);
  • 再次遍历字典,将第一个只出现过一次的字符返回即可。

知识点

从python3.6开始的字典默认是有序的,而且效率比之前的无序字典更高,具体分析可参考为什么Python 3.6以后字典有序并且效率更高?

发表评论

电子邮件地址不会被公开。