首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 说明你所设计算法的时间复杂度与空间复杂度。
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 说明你所设计算法的时间复杂度与空间复杂度。
admin
2014-04-17
36
问题
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求:
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
时间复杂度分析:在整个算法过程中,遍历了两遍字符串,所以时间复杂度为O(n)。 空间复杂度分析:算法中使用了一个长度为256的数组,而此数组的长度不随字符串的长度增加而增加,恒为256这个常数,所以空间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/7exi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述十字军运动(十字军东征)发生的背景、过程及其影响。
简述蒙古西征的具体过程及其对中亚等地区的影响。(东北师范大学1999年世界中古史真题;南京大学2001年综合卷真题;东北师范大学2002年世界中古史真题)
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
战国初期,上党地区在下列哪一个国家的控制范围之内?()
简述当代科学技术革命兴起的背景、特点及影响。
二战后主要资本主义国家经济恢复和发展的杠杆是()①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
下列有关《布列斯特和约》的说法中,错误的一项是()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
随机试题
水中的化学性污染物的危害不包括
以下哪项不是阴虚血热经期延长的主证
大中型、小型企业药品抽样检验的批数,分别是不应少于进货批次的
某市拟在城市东北郊区新建1座日处理能力为1000t的生活垃圾焚烧电厂,工程建设内容包括2500t/d的垃圾焚烧炉(机械炉排炉)、垃圾贮坑、焚烧发电系统、烟气净化系统、污水处理站等,年运行333d,每天运行24h。人炉生活垃圾含有C、H、O、N、S、Cl等元
【背景资料】某污水处理厂扩建工程由原水管线、格栅间、提升泵房、沉沙池、初沉池等组成,承包单位以2250万元中标。原水管线基底标高为一6.00m(地面标高为±0.00m),基底处于砂砾层内,且北邻S河,地下水位标高为一3.00m。
多媒体计算机的声卡对声音信号的数字化处理包括()。
犯罪嫌疑人蔡某涉嫌杀人,侦查人员为了查明案件事实,依法对其进行讯问,此时,蔡某聘请了律师吴某,则吴某可以为其()。
政府应当是公共产品和服务的唯一提供者。()
大象:鼻子
早期人类的骸骨清楚地显示他们比现代人更少有牙齿方面的问题。因此,早期人类的饮食很可能与今天的非常不同。以下哪项陈述最能强化上述论证?
最新回复
(
0
)