387字符串中第一个唯一的字符

发表时间:2020-12-25

哈希

遍历两趟字符串

class Solution:
    def firstUniqChar(self, s: str) -> int:
        ans = 0
        mp = Counter(s) 
        for i,ch in enumerate(s):
            if mp[ch] == 1:
                return i
        return -1  

时间复杂度 O ( n ) O(n) O ( n )
空间复杂度 O ( ∣ s ∣ ) O(|s|) O ( s ) ∣ s ∣ |s| s 是字符的数量

改进哈希

遍历一趟字符串,第二趟遍历hash table

class Solution:
    def firstUniqChar(self, s: str) -> int:
        ans = 0
        mp = dict()
        for i,ch in enumerate(s):
            if ch in mp:
                mp[ch] = -1
            else:
                mp[ch] = i

        for k,v in mp.items():
            if v!=-1:
                return v
        return -1  

因为python里dict的key是按照加入顺序构成的,所以可以直接便利

时间复杂度 O ( n ) O(n) O ( n )
空间复杂度 O ( ∣ s ∣ ) O(|s|) O ( s ) ∣ s ∣ |s| s 是字符的数量

相比遍历两次字符串,效率更高

队列

感觉没有任何优势的写法
在这里插入图片描述

class Solution:
    def firstUniqChar(self, s: str) -> int:
        position = dict()
        q = collections.deque()
        n = len(s)
        for i, ch in enumerate(s):
            if ch not in position:
                position[ch] = i
                q.append((s[i], i))
            else:
                position[ch] = -1
                while q and position[q[0][0]] == -1:
                    q.popleft()
        return -1 if not q else q[0][1]

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

在这里插入图片描述

文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free