系列专栏：牛客刷题——数据结构与算法🔥 该专栏作为刷题笔记，持续更新中。

推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

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$ 。

4.完成遍历后，此时队列的队首元素就是我们要找的元素。而累积出队数量$x$就是队首元素在字符串中的位置。

这个神奇的思路来自题解：第一个只出现一次的字符_牛客博客 (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.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读