给定一字符串，该字符串中存在若干对相同的字符，设计一个在时间和空间上尽可能高效的算法，找出一对相同字符在该字符串中的最大距离。例如：“KLabcLdecL”，其中第一个“L”和最后一个“L”相距最远，它们在原字符串中的位置相差8，要求：说明你所设计算法

admin2017-04-28 79

问题给定一字符串，该字符串中存在若干对相同的字符，设计一个在时间和空间上尽可能高效的算法，找出一对相同字符在该字符串中的最大距离。例如：“KLabcLdecL”，其中第一个“L”和最后一个“L”相距最远，它们在原字符串中的位置相差8，要求：
说明你所设计算法的时间复杂度和空间复杂度。

选项

答案时间复杂度分析：整个算法过程相当于把数组遍历了一遍，所以时间复杂度为O(n)。空间复杂度分析：算法中最多只需要使用128个数组元素，所以空间复杂度为一常数，表示为O(1)。

解析

转载请注明原文地址:https://kaotiyun.com/show/AXRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

美国主张建立国际联盟的主要目的是()。

第二次世界大战给全人类的启示是()①维护世界和平是当代各国人民的共同任务②必须坚持反对霸权主义和强权政治③必须发展和壮大世界和平力量④必须建立国际政治经济新秩序

规定了电流、电动势、电阻等概念的物理学家是()。

开皇三年，隋文帝下令州县官吏根据户籍簿上登记的年龄，来核对本人体貌，以防诈老诈小逃避租役，是为()。

中国共产党召开七届二中全会的主要目的是()。

唐朝官营手工业中，每年服役二十天，在政府“趋役不尽及别有和雇”的情况下，可“纳资代役”的是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

佛教向亚洲国家传播始于印度的哪个时代?()

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

先天性心脏病姑息性手术中体．肺分流术。其临床效果是

李先生，62岁。先是夜间尿频，后逐步排尿时间延长，尿不净。今下午排不出尿，小腹胀痛来院就诊。护士首先应如何处理

黄柏具有的功效是()龙胆草具有的功效是()

患者，男性，35岁，因肱骨干骨折入院，伤后局部组织肿胀明显。手法复位后行石膏固定。术后护士应注意观察肢端血运。若有血运障碍，下面哪种表现最不可能发生

宪法规定，有关职务连续任职不得超过两届，但下列不受此限的是：

中江贸易(香港)有限公司系中江国际贸易(公司)派驻香港的全资子公司，受总公司的委托为天津中江服装饰品厂对外签约订货。本提单之运输工具于2001年1月16日向天津海关申报进口。

大雁在飞翔时的队形，有时是“一”字形，有时是“人”字形。影响它们飞翔时队形变化的主要因素是()。

你所在铁路派出所打算举办开放日活动。邀请辖区内中小学校师生前来参观，领导让你负责组织安排。你怎么安排?

以下哪些不是法律关系客体中法律意义上的物?()

Thefirsttilingadogistaughtisto【S1】Itshouldnot【S2】toolongforhimtolearncommands.【S3】__orders,such

计算机408

学硕统考专业

美国主张建立国际联盟的主要目的是()。

第二次世界大战给全人类的启示是()①维护世界和平是当代各国人民的共同任务②必须坚持反对霸权主义和强权政治③必须发展和壮大世界和平力量④必须建立国际政治经济新秩序

规定了电流、电动势、电阻等概念的物理学家是()。

开皇三年，隋文帝下令州县官吏根据户籍簿上登记的年龄，来核对本人体貌，以防诈老诈小逃避租役，是为()。

中国共产党召开七届二中全会的主要目的是()。

唐朝官营手工业中，每年服役二十天，在政府“趋役不尽及别有和雇”的情况下，可“纳资代役”的是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

佛教向亚洲国家传播始于印度的哪个时代?()

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

先天性心脏病姑息性手术中体．肺分流术。其临床效果是

李先生，62岁。先是夜间尿频，后逐步排尿时间延长，尿不净。今下午排不出尿，小腹胀痛来院就诊。护士首先应如何处理

黄柏具有的功效是()龙胆草具有的功效是()

患者，男性，35岁，因肱骨干骨折入院，伤后局部组织肿胀明显。手法复位后行石膏固定。术后护士应注意观察肢端血运。若有血运障碍，下面哪种表现最不可能发生

宪法规定，有关职务连续任职不得超过两届，但下列不受此限的是：

中江贸易(香港)有限公司系中江国际贸易(公司)派驻香港的全资子公司，受总公司的委托为天津中江服装饰品厂对外签约订货。本提单之运输工具于2001年1月16日向天津海关申报进口。

大雁在飞翔时的队形，有时是“一”字形，有时是“人”字形。影响它们飞翔时队形变化的主要因素是()。

你所在铁路派出所打算举办开放日活动。邀请辖区内中小学校师生前来参观，领导让你负责组织安排。你怎么安排?

以下哪些不是法律关系客体中法律意义上的物?()

Thefirsttilingadogistaughtisto【S1】______Itshouldnot【S2】______toolongforhimtolearncommands.【S3】______orders,such

Thefirsttilingadogistaughtisto【S1】Itshouldnot【S2】toolongforhimtolearncommands.【S3】__orders,such