当前位置：首页 > news >正文

【牛客刷题-算法】NC31 第一个只出现一次的字符（哈希表、队列两种解法）

news 来源：原创 2024/5/5 2:30:55

系列专栏：牛客刷题——数据结构与算法
🔥 该专栏作为刷题笔记，持续更新中。
推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

文章目录

1.题目描述
2.算法设计思路
3.算法实现
4.运行结果
结束语：

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;
    }
};