387.字符串中的第一个唯一字符 First Unique Character in a String

小咪咪 2022-12-29 14:27 135阅读 0赞

## 题目描述 ##

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

**示例**：

> s = “leetcode”  
> 返回 0  
> s = “loveleetcode”  
> 返回 2

来源：力扣（LeetCode）[链接][Link 1]

## 题解 ##

我自己写的代码显示**超出时间限制**，不知道是什么原因，难道是因为我的时间复杂度是 O ( n 2 ) O(n^2) O(n2)。

class Solution:
        def firstUniqChar(self, s: str) -> int:
            s = list(s)         # 转换为数组
            l = []              # 记录包含重复元素的集合
            for i in range(len(s)):
                index = i
                if s[i] in l:   # 有重复元素，下次不再遍历这个元素
                    continue
                for j in range(i + 1, len(s)):
                    if s[i] == s[j]:
                        l.append(s[j])
                        index += 1
                        continue    # 有重复元素跳出此次循环
                # 如果index经过一轮循环后不变则直接返回index
                if index == i:
                    return i
            return -1

看了官网答案，最简单的题解是使用**哈希映射**统计出字符串中每个字符出现的次数。  
执行用时：88 ms, 在所有 Python3 提交中击败了91.45%的用户；  
内存消耗：14.9 MB, 在所有 Python3 提交中击败了6.54%的用户。

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

[Link 1]: https://leetcode-cn.com/problems/first-unique-character-in-a-string