首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一个含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
38
问题
给定一个含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
学硕统考专业
相关试题推荐
洋务运动时期,首批赴欧海军留学生派出的时间是()。
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题在武王灭商和周公东征的过程中立有大功,或与周有世代同盟关系的异姓贵族也被分封去建立诸侯国家,继续为周王室效力,下列国家:①齐②鲁③燕④宋,属于异姓诸侯国的是(
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:随着商业的发展,唐朝在货币和金融方面有一些重要的进步,以下表述全面的是()
“人身保护法”
中山舰事件
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
将要相互通信双方怎样进行建立TCP连接?在TCP报文段的首部中只有端口号而没有IP地址,当TCP将其报文段交给IP层时,IP协议怎样知道目的IP地址呢?为什么把IP地址又称为“虚拟地址”,把TCP连接说成是“虚连接”?假设在建立连接时使用2次握手而非3次握
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
随机试题
患者,女,45岁。患水肿10年,近来小便不通,面色苍白,呕吐清水,面色晦滞,畏寒肢冷,大便正常,舌淡苔白滑,脉沉细。治疗应首选
《中华人民共和国义务教育法》规定,()确定义务教育阶段的教学制度、教育教学内容、课程设置,改革考试制度,并改进高级中等学校招生办法,推进实施素质教育。
片剂四用测定仪可测定的项目是
不属于婴儿总热量分配的是
把控制报告按照()的不同进一步细分,是工程项目总控的成果之所在。
洁净空调系统调试和试运行应具备的条件有()。
关于保证贷款,下列说法错误的是()。
战略性人力资源管理面临的障碍有()。
品牌资产的价值与()等因素有关。
单击“演示文稿”按钮,然后按照题目要求完成下面的操作。注意:以下的文件必须保存在考生文件夹下。打开考生文件夹下的演示文稿yswg.pptx,根据考生文件夹下的文件“PPT-素材.docx”,按照下列要求完善此文稿并保存。为第一张幻灯
最新回复
(
0
)