首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 说明你所设计算法
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 说明你所设计算法
admin
2017-04-28
37
问题
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求:
说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
时间复杂度分析:整个算法过程相当于把数组遍历了一遍,所以时间复杂度为O(n)。 空间复杂度分析:算法中最多只需要使用128个数组元素,所以空间复杂度为一常数,表示为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/AXRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述《拉巴洛条约》签订的背景、条约的主要内容及其意义。
下列关于塞尔维乌斯改革的叙述错误的是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
罗马帝国疆域扩张到顶点是在()统治时期。
在巴黎和会上,法国要求严厉制裁德国的目的是()。
把中国第一次工人运动的高潮推向顶点的是()。
太平天国作为几千年来农民运动的高峰,所遇到的历次农民运动中不曾有过的新情况是(
以下()协议完成了从网卡到IP地址的映射。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
循环队列用数组A[0..m~1]存放其元素值,已知其头尾指针分别为front和rear,则当前元素个数为()。
随机试题
威廉.邓恩归纳三种预测方法有_________、________、________。
Access2010数据库对象中,_____是应用程序和用户之间的接口界面,是创建数据库应用系统最基本的对象。
付款是指付款人依据票据支付票据金额,以消灭票据的关系,属票据行为。( )
保密条款是指除当法律要求或/和遵守相关监管机构/权威机构(视情况而定)的披露要求外,投资协议中规定投资方应对投资中了解的目标公司的()和其他信息承担保密义务,保证不将这些信息泄露给第三方。
证券公司通过基于互联网或移动通讯网络的网上证券交易系统,向客户提供用于下达证券交易指令、获取成交结果的服务方式是()。
通常,公司债券的违约风险越大,则信用等级就越低,投资人要求的回报率也越高。()
在交际场合中,称谓很重要,通过它能反映人与人之间的关系,显示一个人的修养,在某种程度上也反映了社会的风尚。()
1936年9月1日,中共中央发出党内指示,明确提出党的总方针是()
IP地址块59.67.79.128/28、59.67.79.144/28和59.67.79.160/27经聚合后可用地址数为()。
AccordingtoMr.Bacon.peoplekeepsnakesbecause
最新回复
(
0
)