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

admin2014-04-17  40

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

选项

答案时间复杂度分析:在整个算法过程中,遍历了两遍字符串,所以时间复杂度为O(n)。 空间复杂度分析:算法中使用了一个长度为256的数组,而此数组的长度不随字符串的长度增加而增加,恒为256这个常数,所以空间复杂度为O(n)。

解析
转载请注明原文地址:https://jikaoti.com/ti/FuajFFFM
0

最新回复(0)