描述
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
数据范围： 0 ≤ n ≤ 10000，且字符串只有字母组成。
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例1
输入："google"
返回值：4
示例2
输入："aa"
返回值：-1
方法一：哈希表统计频率（推荐使用）
知识点：哈希表
哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在 O(1) 时间内得到 value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。
思路：
既然要找第一个只出现一次的字符，那只要我们统计每个字符在字符串中出现的次数，后续不就可以找到第一个只出现一次的字符了吗？
统计频率可以建立一个哈希表，遍历字符串的同时，统计每个字符出现的频率，然后再从头遍历一次字符串，在哈希表中查看每个字符串的频率，找到第一个只出现一次的字符串，返回位置，如果没找到返回 -1 即可。
具体做法：
- step 1：遍历一次字符串，对于每个字符，放入哈希表中统计出现次数。
- step 2：再次遍历字符串，对于每个字符，检查哈希表中出现次数是否为1，找到第一个即可。
- step 3：遍历结束都没找到，那就是没有，返回 -1.
代码：
class Solution {
public:
int FirstNotRepeatingChar(string str) {
unordered_map<char, int> mp;
//统计每个字符出现的次数
for(int i = 0; i < str.length(); i++)
mp[str[i]]++;
//找到第一个只出现一次的字母
for(int i = 0; i < str.length(); i++)
if(mp[str[i]] == 1)
return i;
//没有找到
return -1;
}
};
运行时间：4ms
超过22.02% 用C++提交的代码
占用内存：640KB
超过12.91%用C++提交的代码
复杂度分析：
时间复杂度： O(n)，其中 n 为字符串长度，两次单独的遍历
空间复杂度： O(1)，哈希表的大小最多不会超过字符集，即52个字符，属于常数空间
方法二：队列+哈希表统计位置（扩展思路）
知识点：队列
队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。
思路：
上述方法一遍历了两次，有些繁琐，我们能不能在统计频率的过程中就找到第一个只出现一次的字符呢？利用先进先出的队列找到第一个位置！
首先我们还是利用了哈希表，但是这次我们不是统计频率，而是统计每个字符出现位置。遍历字符串，如果遇到哈希表中没有的字符，我们入哈希表，同将字符和位置同时各自入队，后续如果遇到了哈希表中出现的字符，那么这个字符势必不可能是我们要找的只出现一次的字符，在哈希表中将其位置置为 -1：
//位置置为-1
mp[str[i]] = -1;
然后弹出队列中在前面的哈希表中位置为-1的字符。因为队列是先进先出，因此队列头记录的字符一定是第一次只出现一次的字符。
while(!q.empty() && mp[q.front().first] == -1)
q.pop();
空队列则代表没有找到。
具体做法：
- step 1：利用哈希表记录字符串中出现过的字符的位置，利用两个队列分别记录字符与下标位置（C++可以用pair）。
- step 2：遍历字符串，如果是没有遇到过的字符，就加入哈希表记录位置，同时字符与下标分别入队。
- step 3：遇到出现过的字符，就将其哈希表中的下标置为 -1，然后弹出队列首部所有重复的字符，即位置为 -1 的字符。
- step 4：最后队列中剩余的队首就是第一个只出现一次的字符，因为其他的重复字符都被弹出了，队列为空就代表没有不重复的字符。
图示：
代码：
class Solution {
public:
int FirstNotRepeatingChar(string str) {
//统计字符出现的位置
unordered_map<char, int> mp;
queue<pair<char, int> > q;
for(int i = 0; i < str.length(); i++){
//没有出现过的字符
if(!mp.count(str[i])){
mp[str[i]] = i;
q.push(make_pair(str[i], i));
//找到重复的字符
}else{
//位置置为-1
mp[str[i]] = -1;
//弹出前面所有的重复过的字符
while(!q.empty() && mp[q.front().first] == -1)
q.pop();
}
}
return q.empty() ? -1 : q.front().second;
}
};
运行时间：4ms
超过22.02% 用C++提交的代码
占用内存：644KB
超过12.82%用C++提交的代码
复杂度分析：
时间复杂度： O(n)，对字符串进行一次遍历，内循环整个过程中才最多弹出52次
空间复杂度： O(1)，哈希表和队列的大小最多不会超过字符集，即52个字符，属于常数空间
