设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 给出算法的基本设计思想。

admin2014-04-17  33

问题 设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求:
给出算法的基本设计思想。

选项

答案基本设计思想:算法的策略是构建一个简单的散列表,由于本题需要构建的是字符的散列表,而一个字符(Char)占8个二进制位,符出现的次数。这样就创建了一个大小为256,以字符ASCⅡ码为键值的散列表。当第一遍遍历这个数组时,每碰到一个字符,在散列表中找到对应的项并把出现的次数增加一次。第一遍遍历完后,进行第二遍遍历,就能直接从散列表中得到每个字符出现的次数了。

解析
转载请注明原文地址:https://kaotiyun.com/show/sYxi777K
0

最新回复(0)