首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一个含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
43
问题
给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组(-5,3,2,3)中未出现的最小正整数是1;数组{1,2,3)中未出现的最小正整数是4。要求:
说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
时间复杂度:遍历A一次,遍历B一次,两次循环内操作步骤为O(1)量级,因此时间复杂度为O(n)。空间复杂度:额外分配了B[n],空间复杂度为O(n)。
解析
转载请注明原文地址:https://jikaoti.com/ti/RMGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列选项中,不属于西汉农业发展状况的是()
米勒兰事件
以下()协议完成了从网卡到IP地址的映射。
下列各种情况中,应采用异步通信方式的是()。
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
分时系统里,在条件相同的情况下,通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间,请简要解释之。
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
UDP的报文头部不包括()。
下列关于RISC的叙述中,错误的是()。
下面关于进程的叙述中,正确的是()。
随机试题
患者,男,25岁,C5—6骨折合并四肢瘫痪,无感染病灶出现高热。下列护理措施中错误的是
女性,16岁。双下肢重度浮肿1个月,突然四肢厥冷、头晕10分钟来诊,尿量100ml/日,体检:血压80/60mmHg(10.6/8kPa),颈静脉塌陷,血红蛋白16.0g/L,HCt0.381/L,SCr150μmol/L,血白蛋白20g/L。最可能的诊断
商品住房在销售时,购房者与售房单位应当签订有关维修资金缴纳约定。购房者应当按购房款()的比例向售房单位缴纳维修资金。
设D是曲线y=x2与y=1所围闭区域,
下列的市政职能中,()属于传统职能。
在中国文学艺术界联合会第九次全国代表大会上,胡锦涛同志强调广大文艺工作者要始终坚持德艺双馨,更加自觉、更加主动地承担起弘扬文明道德风尚的历史责任。()
某被害人有充分证据证明犯罪嫌疑人的犯罪行为,而当地公安机关却做出不立案的决定,被害人到当地人民检察院反映,对此,人民检察院应当()。
有人说旅行的好处是离开家,有人说是回到家。谈谈你的看法?
乐视:优酷:土豆
若有定义:inta=0,b=0,c=0,d=0;,有C语言表达式(a++&&b++):c++:d++,以下关于其执行顺序的叙述正确是
最新回复
(
0
)