LeetCode 387. 字符串中的第一个唯一字符_编程题:字符串中的第一个唯一字符

题目

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

详见：387. 字符串中的第一个唯一字符

思路

1. 哈希存储出现次数，第一次遍历字符串，存储每个字符出现的次数，第二次遍历字符串，如果该字符只出现一次，则返回它的索引
2. find函数，rfind() 从后向前查找字符第一次出现的位置，find() 从前向后查找字符第一次出现的位置，遍历字符串，如果字符的第一个索引和最后一个索引是同一个位置，则返回该索引

队列，也可以借助队列找到第一个不重复的字符，队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c
与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为−1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。在遍历完成后，如果队列为空，说明没有不重复的字符，返回−1，否则队首的元素即为第一个不重复的字符以及其索引的二元组。在维护队列时，我们使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，我们也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，我们才需要将它移除。
来源：LeetCode

代码

方法一：哈希存储出现次数

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int>str;
        for(auto ch : s){
            str[ch]++;
        }
        for(int i = 0; i < s.size(); i++){
            if(str[s[i]] == 1){
                return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 时间复杂度：O(n)
• 空间复杂度：O(∣Σ∣)

方法二： find函数

class Solution {
public:
    int firstUniqChar(string s) {
        for(int i = 0; i < s.size(); i++){
            if(s.find(s[i]) == s.rfind(s[i])){
                return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11

方法三：队列

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> position;
        queue<pair<char, int>> q;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (!position.count(s[i])) {
                position[s[i]] = i;
                q.emplace(s[i], i);
            }
            else {
                position[s[i]] = -1;
                while (!q.empty() && position[q.front().first] == -1) {
                    q.pop();
                }
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22