首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 说明你所设计算法的时间复杂度与空间复杂度。
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 说明你所设计算法的时间复杂度与空间复杂度。
admin
2014-04-17
32
问题
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求:
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
时间复杂度分析:在整个算法过程中,遍历了两遍字符串,所以时间复杂度为O(n)。 空间复杂度分析:算法中使用了一个长度为256的数组,而此数组的长度不随字符串的长度增加而增加,恒为256这个常数,所以空间复杂度为O(n)。
解析
转载请注明原文地址:https://jikaoti.com/ti/FuajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
汉元帝建昭三年(前36),西域副校尉陈汤发西域各国兵远征康居,击杀了挟持西域各国并与归汉的呼韩邪单于为敌的(),匈奴的势力在西域消失,汉和西域的通道大为安全。
重庆谈判的焦点问题是()
简述当代科学技术革命兴起的背景、特点及影响。
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
1543年发表解剖学专著《人体结构论》的是()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
1543年,发表了解剖学专著《人体结构》的是()。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
随机试题
Althoughit’stoughfindingajobthesedays,Henrygota________inafamouscompany.
临床上使用的辐照红细胞主要是为了A.预防非溶血性发热反应B.预防过敏反应C.预防TA-GVHDD.预防输血传播的疾病E.需要长期依赖输血治疗的患者减少输血次数
会计数据一般保存在()中。
下列关于我国历史的说法,正确的是()。
舞榭歌台,___________。(辛弃疾《永遇乐.京口北固亭环古》)
蒸发冷却是指液体在蒸发成气体的过程中会吸热,从而降低周围的温度起到冷却的效果。蒸发冷却效应是指在目的或志趣相同的人们组成的社会团体中,团体的价值跟液体的整体温度类似,当价值较高的成员离开社团后,社团自身的平均价值会降低。根据上述定义,下列属于蒸发冷却效应的
羊群效应
ThehomelessmakeupagrowingpercentageofAmerica’spopulation.【B1】homelessnesshasreachedsuchproportionsthatlocalgov
YouwanttoinstallWindows2000Professionalon45newcomputersonyourcompany’snetwork.YoufirstinstallWindows2000Prof
在关系模型中,实现“关系中不允许出现相同的元组”的约束是通过______。
最新回复
(
0
)