写点什么

第一个只出现一次的字符 (哈希表、队列两种解法)

作者:清风莫追
  • 2022 年 10 月 05 日
    湖南
  • 本文字数:979 字

    阅读完需:约 3 分钟

第一个只出现一次的字符 (哈希表、队列两种解法)

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

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



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.在每个字母入队时,将它与队首元素比较;若相同,则将队首元素出队,同时统计出队元素数量


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


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

成功通过!




结束语:

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




感谢阅读


发布于: 刚刚阅读数: 3
用户头像

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

评论

发布
暂无评论
第一个只出现一次的字符 (哈希表、队列两种解法)_数据结构_清风莫追_InfoQ写作社区