字符串首次单个出现的字符

2016-11-19 17:06 阅读 642 次 评论 0 条

00:00/00:00

首次单次单个出现的字符

问题:一个字符串中查找第一个只出现一次的字符。要求复杂度为O(N).

思路:这道题依旧是有时间复杂度限制的,表明该算法是呈线性变化的。这里我们用到了hashtable,也就是哈希表,也叫散列表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做哈希表。我们只想遍历一次字符串(即单层循环),那么必然就需要将某些信息记录下来,这里记录的当然就是每个字符出现的次数。对于只出现一次的字符,也必然会在哈希表里面记录一次,最先记录一次的就是最先出现的单个字符,直接break就得到最终的结果。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:字符串首次单个出现的字符 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情