1.题目描述
描述
在一个长为n的字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
数据范围：0≤n≤10000，且字符串只有字母组成。
要求：空间复杂度 O(n)，时间复杂度 O(n)
2.算法设计思路
关键信息：字符串只由字母组成（区分大小写）。
思路一
1.建一个数组，长度为52（一共有26个字母）。
2.遍历字符串，统计各个字母出现的次数。
3.再次从头遍历字符串，找到出现次数为1的字母时停下来，返回此时在字符串中的位置。
4.若未找到出现次数为1的字母，则返回-1。
补充：哈希表（散列表）
在实际的代码实现中，我们要如何将字母与数组的下标对应起来？
我们可以设置一个散列函数，将字母作为输入，散列函数将计算出对应的下标值，而该下标位置就存储字母出现的次数。
关于哈希表的介绍，有一篇文章真的写的很棒，大家可以参考：来吧！一文彻底搞定哈希表！_庆哥Java的博客-CSDN博客
思路二
1.建一个队列
2.遍历字符串，同时将字母入队。
3.在每个字母入队时，将它与队首元素比较；若相同，则将队首元素出队，同时统计出队元素数量 x xx 。
4.完成遍历后，此时队列的队首元素就是我们要找的元素。而累积出队数量x xx就是队首元素在字符串中的位置。
这个神奇的思路来自题解：第一个只出现一次的字符_牛客博客 (nowcoder.net)
3.算法实现
注：这里并不是完整代码，而只是核心代码的模式
下面是思路一的C++实现：
class Solution { public: int hash(char ch){ int index = 0; if('a' <= ch && ch <= 'z') index = ch - 'a'; else if('A' <= ch && ch <= 'Z') index = ch - 'A' + 26; return index; } int FirstNotRepeatingChar(string str) { int a[52] = {};//统计字母出现次数 for(int i = 0; str[i] != '\0'; i++){ a[hash(str[i])]++; } for(int i = 0; str[i] != '\0'; i++){ if(a[hash(str[i])] == 1) return i; } return -1; } };
思路二的代码可以参考上面的题解。
4.运行结果
成功通过！
