首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 说明你所设计算法的时间复杂度与空间复杂度。
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 说明你所设计算法的时间复杂度与空间复杂度。
admin
2014-04-17
37
问题
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求:
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
时间复杂度分析:在整个算法过程中,遍历了两遍字符串,所以时间复杂度为O(n)。 空间复杂度分析:算法中使用了一个长度为256的数组,而此数组的长度不随字符串的长度增加而增加,恒为256这个常数,所以空间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/7exi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
国民政府对日宣战的时间是()。
北魏建立和统一的时间分别是()。
在下列各项中,哪些属于苏俄实行“新经济政策”的前提条件?()。①有巩固的工农联盟②国家掌握了一切经济命脉③国民经济已明显恢复④帝国主义武装干涉已被粉碎
巴黎公社采取的带有无产阶级专政性质的措施有()。①公社人员由民主选举产生②没收逃亡资本家的工厂,交给工人合作社管理③取消旧的国家机器,建立:亡人阶级自己的国家机构④工职人员年薪不得超过熟练工人的工资
()是一部上起传说中的黄帝,下迄汉武帝时期的中国通史,是中国历史上第一部内容完整、结构周密的历史著作。
毛泽东在《论持久战》中指出,中国抗日战争取得最后胜利最为关键的阶段是()。
古埃及中王国时期出现了一个新兴的手工业部门,对世界文明做出了巨大贡献。这一新兴的手工业部门是()。
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争。这一古老文件是()
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:写出图G的邻接矩阵A。
随机试题
己知函数f(x)在[0,1]上可导,f(x)>0,f(0)=1,且在[0,1)满足等式求函数f(x).
以下关于口服降糖药叙述错误的是
治疗米面薯芋等淀粉性食滞证,宜首选
某县政府为了加强社会治安综合治理,从事业单位抽调李某等五人组成治安巡逻大队。县公安局为他们发放了工作证,配备了手铐等警械,并规定其职责是负责维持县城集市贸易区的治安。一日,李某等人巡逻至城西区农贸市场时,发现张某等人在打架斗殴、寻衅滋事。遂作出对张某处1
逻辑函数F=的简化结果是()。
对一个文件来说,必须有()。
下列项目中,按税法规定可以免征或不征土地增值税的有()。
通过观察儿童在日常生活、游戏、学习和劳动等活动中的表现,以研究儿童心理的特点和规律,这种研究方法是()。
Employee的表结构为:职工号、单位号、工资,查询单位号为"002"的所有记录存储于临时表文件info中,正确的SQL命令是
在中国,食物是用大的公用盘子(communalplate)来盛装的,而且基本上都会提供公用的筷子来将食物从公用的盘子里弄到你自己的盘子里。如果有公用的筷子就用公共的筷子来分开食物。如果没有,或是不确定有没有,你可以先等一等,看其他人是怎么做的,然后效仿就
最新回复
(
0
)