博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
求字符串中第一个只出现一次的字符
阅读量:4449 次
发布时间:2019-06-07

本文共 472 字,大约阅读时间需要 1 分钟。

问题描述:给定一个字符串,假设字符串中只包含字母和数字,求出这个字符串中第一个只出现一次的字符。

分析:这个题目想要做出来还是比较简单的,关键是如何用高效的方法求解。这里我提供两种方法:

         解法一:蛮力法。具体思想为,从第一位开始,拿每一位和后面的每一位进行比较,如果没有出现,则直接输出这个字符。

                    如果出现,则从第二位开始,再和后面的每一位进行比较,依次类推。

                    算法的时间复杂度为O(n^2).

         解法二:哈希法。采用两次扫描即可实现。需要提前构建一个哈希表,把字符当成key值,把出现的次数当成value值,并初始化。

                    第一次扫描,统计出现的每个字符的次数,存到哈希表中;

                    第二次扫描,从字符串第一位开始,查看对应的value是否为1,如果为1,直接返回该字符,算法结束,否则,接着扫描。

                    算法的时间复杂度为O(n).空间复杂度为O(1).这种方法属于典型的空间换时间。

 

        由于算法比较简单,我就不再写具体的代码了,读者可以自行验证。

转载于:https://www.cnblogs.com/guozhenqiang/p/5483609.html

你可能感兴趣的文章
P3332 [ZJOI2013]K大数查询
查看>>
P2568 GCD
查看>>
将程序从Flash搬运到RAM中运行总结(转载)
查看>>
storm的trident编程模型
查看>>
算法导论 10.2-7
查看>>
【两段连续不重合子序列和最大】 动态规划
查看>>
MyISAM 和 InnoDB 索引的区别
查看>>
字符串处理,取出按指定分割符号(非空格)进行字符串切割
查看>>
linux下统计文本行数的各种方法(二)
查看>>
java中的匿名内部类
查看>>
读书笔记——计算机科学导论
查看>>
php环境搭建
查看>>
类和对象-2
查看>>
使用UltraEdit+BCC5.5搭建C语言学习环境(转)
查看>>
485收发控制器:
查看>>
mssql死锁
查看>>
读取iOS plist文件 (其实类似读取xml文件)
查看>>
wps的几个优点
查看>>
Swift 可选链
查看>>
Servlet的入门案例
查看>>