首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 说明你所设计算法
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 说明你所设计算法
admin
2017-04-28
72
问题
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求:
说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
时间复杂度分析:整个算法过程相当于把数组遍历了一遍,所以时间复杂度为O(n)。 空间复杂度分析:算法中最多只需要使用128个数组元素,所以空间复杂度为一常数,表示为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/AXRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述罗马法学的发展情况。
试比较南斯拉夫、苏联、匈牙利的经济发展模式。
开皇三年,隋文帝下令州县官吏根据户籍簿上登记的年龄,来核对本人体貌,以防诈老诈小逃避租役,是为()。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
1947年,苏联一些农村的干部和群众,为了调动广大群众生产积极性,在管理制度方面进行改革,其主要措施是()。
在1875年宪法中关于法国立法权的叙述,不正确的是()。
系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。
决定把苏联由农业国变成工业国的主要目的是()
某浮点机字长16位,其浮点数格式为:阶码5位(含1位阶符),采用补码表示,尾数11位(含1位数符),采用补码表示,且尾数为规格化形式。已知X=0.1011000011×20.0101,Y=0.0001100000×20.1000,试求X+Y.要求写出详细的
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:该指令系统最多可有多少条指令?该计算机最多有
随机试题
联系实际说明如何培养健康的情绪。
笼养蛋鸡疲劳症又称为
硬质树脂嵌体牙体预备要求与金属嵌体的区别点
行政复议的期限最长不得超过()日。
水体污染源主要包括()。
(操作员:赵主管;账套:301账套;操作日期:2015年1月31日)选择单据号为0015(单据类型为应收借项)的应收单,生成凭证。
注册税务师从事企业所得税纳税审核代理实务时,直接材料成本的审核一般应从审阅材料和生产成本明细账人手,抽查有关的费用凭证,验证企业产品直接耗用材料的数量、计价和材料费用分配是否真实合理。主要采用的方法描述中不正确的是()。
某投资项目的建设期为0,则直接利用年金现值系数计算该项目内部收益率指标所要求的前提条件是()。
DearMr.Harrison,Itwasapleasurespeakingwithyouonthephonethisafternoon.Iamveryhappytoacceptthepositiono
ANiceCupofTeaTheLegendaryOriginsofTeaA)ThestoryofteabeganinancientChinaover5,000yearsago.Accordingto
最新回复
(
0
)