云野 ☁️

14、字符串中的第一个唯一字符

|
|
访问
本文共628字。
展开

题目描述

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

示例 1：
输入: s = “leetcode”
输出: 0

示例 2:
输入: s = “loveleetcode”
输出: 2
链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string

方法1、哈希表存储字符频次

使用哈希表存储字符出现的次数。

思路：先遍历一次，得到所有字符出现的次数。（这个用内置函数collections.Counter()即可。）

再遍历一次，直接返回第一次出现1次的字符的索引。遍历完毕还没有符合的字符，就返回-1。

时间复杂度：O(n)。遍历两次。2n。

空间复杂度：$O(|\Sigma|)$，其中 $\Sigma$ 是字符集，在本题中 s 只包含小写字母，因此 $|\Sigma| \leq 26$。我们需要 $O(|\Sigma|)$的空间存储哈希映射。

1
2
3
4
5
6
7
class Solution:
    def firstUniqChar(self, s: str) -> int:
        co = collections.Counter(s)
        for i,x in enumerate(s):
            if co[x]==1:
                return i
        return -1

方法2、哈希表存储字符索引

思路：构建空字典。第一次遍历，得到所有字符对应的索引。如果字符已存在于字典，对应字典值改为-1。

第二次遍历字典，直接返回第一个字典值不为-1的值。遍历完还没有符合的值，返回-1。

时间复杂度：同1

空间复杂度：同1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def firstUniqChar(self, s: str) -> int:
        # 哈希表存储字符索引
        di = dict()
        for i,x in enumerate(s):
            if x in di:
                di[x]=-1
            else:
                di[x]=i
        for k in di:
            if di[k] != -1:
                return di[k]
        return -1

方法3、队列

队列的特点：先进先出。适合用来找第一次满足某个条件的元素。

思路：创建一个空字典和一个空队列。

遍历第一次，（只需要遍历一次）

如果字符不在字典中。字典存储字符和索引；二维队列存储字符和索引。

如果字符在字典中，字典字符的索引赋为-1，且二维队列中如字符存在队列首位，pop掉。

遍历完毕，输出队列首位的索引。

时间复杂度和空间复杂度同1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def firstUniqChar(self, s: str) -> int:
        # 哈希表存储字符索引, 队列存储索引，先进先出
        di = dict()
        q = collections.deque()
        for i,x in enumerate(s):
            if x not in di:
                di[x] = i
                q.append((x,i))
            else:
                di[x]=-1
                while q and di[q[0][0]] == -1:
                    q.popleft()
        return -1 if not q else q[0][1]