首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组(-5,3,2,3)中未出现的最小正整数是1;数组{1,2,3)中未出现的最小正整数是4。要求: 说明你所设计算法的时间复杂度和空间复杂度。
给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组(-5,3,2,3)中未出现的最小正整数是1;数组{1,2,3)中未出现的最小正整数是4。要求: 说明你所设计算法的时间复杂度和空间复杂度。
admin
2019-08-17
42
问题
给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组(-5,3,2,3)中未出现的最小正整数是1;数组{1,2,3)中未出现的最小正整数是4。要求:
说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
时间复杂度:遍历A一次,遍历B一次,两次循环内操作步骤为O(1)量级,因此时间复杂度为O(n)。空间复杂度:额外分配了B[n],空间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/4KCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
宗教问题已成为某些国家和地区之间冲突的主要原因。信仰“真主”安拉,以《古兰经》为经典的宗教是()
波士顿倾茶事件
以下()协议完成了从网卡到IP地址的映射。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
在操作系统中,P,V操作是一种()。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
相对于单一内核结构,采用微内核结构设计实现操作系统具有诸多好处,但是,()并不是微内核的优势。
路由器采用()方式来发送IP分组。
TCP使用()机制来进行流量控制。
以下关于计算机存储器件的叙述,()是不正确的。
随机试题
下列第一审刑事案件,哪些应当由中级人民法院管辖?()
患者,女性,35岁。步行时后仰跌倒,右手掌撑地,伤后1小时,右肩痛,不敢活动。检查:右肩方肩畸形,Dugas征(+)。需要对右肩关节做的辅助检查是
病人缺乏用药依从性,导致治疗失败的表现有
2014年2月5日,马某与陈某订立一份房屋买卖合同,约定陈某购买马某的房屋一套(以下称1号房),价格80万元。并约定,合同签订后一周内陈某先付20万元,交付房屋后付30万元,办理过户登记后付30万元。2月8日,梁某得知马某欲将该房屋出卖,表示愿出90万元购
“窗下一副繁华的街景”属于()。
Heisveryclean.Hismindisopen.
ARP攻击造成网络无法跨网段通信的原因是(8)。
Peoplewhoarehitbylightningandsurviveoftenhavelong-termeffects.Thesemayincludememoryloss,sleepdisorders,muscle
Inthepushtocuttheamountofcarbonwereleaseintotheatmosphere,solutionsusuallyfocusonhowtoreduceourpoweruseo
A、Itmaybelessdamagingthanpreviouslybelieved.B、Therewillneverbeagreementonitsharmtopeople.C、Itmayprovetobe
最新回复
(
0
)