题目
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
思路
- 哈希存储出现次数，第一次遍历字符串，存储每个字符出现的次数，第二次遍历字符串，如果该字符只出现一次，则返回它的索引
- 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; } };
- 时间复杂度：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; } };
方法三：队列
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; } };
