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

admin2017-04-28 42

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。

中华人民共和国恢复了在联合国合法席位的时间是()。

关于垄断组织的积极作用，不正确的说法是()。

系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。

中华人民共和国恢复在联合国合法席位的时间是()。

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

把中国第一次工人运动的高潮推向顶点的是（）。

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

创伤后应激症的反应通常在创伤事件发生后的（　　）个月内会逐渐减少。

患者女性，47岁。患风湿性心脏病20余年，近日发热、咳嗽，夜间睡眠中出现阵发性呼吸困难，面色青紫，出汗，双肺底部有湿性啰音。下列咳痰性质哪一项符合该例患者

实证的病机特点是疾病向愈的病机特点是

当边坡土体裂缝具有加速趋势，必须立即采取()方法，保持土体稳定。

脉压差是衡量人体供血功能的指标之一，我国健康成年人安静时的脉压差介于()。

从中国传统法文化的角度解释下面这段文字的真实含义。“本其事而原其志。志善而违于法者,免;志恶而合于法者,诛。”

关于法律规范，下列说法错误的是()。

A—groceryJ—furnitureshopB—roastmeatshopK—electricalapplianceshopC—foodanddrinkshopL—photographicstudioD—de

计算机408

学硕统考专业

下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。

中华人民共和国恢复了在联合国合法席位的时间是()。

关于垄断组织的积极作用，不正确的说法是()。

系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。

中华人民共和国恢复在联合国合法席位的时间是()。

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

把中国第一次工人运动的高潮推向顶点的是（）。

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

创伤后应激症的反应通常在创伤事件发生后的（ ）个月内会逐渐减少。

患者女性，47岁。患风湿性心脏病20余年，近日发热、咳嗽，夜间睡眠中出现阵发性呼吸困难，面色青紫，出汗，双肺底部有湿性啰音。下列咳痰性质哪一项符合该例患者

实证的病机特点是疾病向愈的病机特点是

当边坡土体裂缝具有加速趋势，必须立即采取()方法，保持土体稳定。

脉压差是衡量人体供血功能的指标之一，我国健康成年人安静时的脉压差介于()。

从中国传统法文化的角度解释下面这段文字的真实含义。“本其事而原其志。志善而违于法者,免;志恶而合于法者,诛。”

关于法律规范，下列说法错误的是()。

A—groceryJ—furnitureshopB—roastmeatshopK—electricalapplianceshopC—foodanddrinkshopL—photographicstudioD—de

创伤后应激症的反应通常在创伤事件发生后的（　　）个月内会逐渐减少。