首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一个含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
25
问题
给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组(-5,3,2,3)中未出现的最小正整数是1;数组{1,2,3)中未出现的最小正整数是4。要求:
给出算法的基本设计思想。
选项
答案
题目要求算法时间上尽可能高效,因此采用空间换时间的办法。分配一个用于标记的数组B[n],用来记录A中是否出现了1~n中的正整数,B[0]对应正整数1,B[n-1]对应正整数n,初始化B中全部为0。由于A中含有n个整数,因此可能返回的值是1~n+1,当A中n个数恰好为1~n时返回n+1。当数组A中出现了小于等于0或者大于n的值时,会导致1~n中出现空余位置,返回结果必然在1~n中,因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。经过以上分析可以得出算法流程:从A[0]开始遍历A,若0<A[i]<=n,则令B[A[i]-1]=1;否则不做操作。对A遍历结束后,开始遍历数组B,若能查找到第一个满足B[i]==0的下标i,返回i+1即为结果,此时说明A中未出现的最小正整数在1~n之间。若B[i]全部不为0,返回i+1(跳出循环时i=n,i+1等于n+1),此时说明A中未出现的最小正整数是n+1。
解析
转载请注明原文地址:https://kaotiyun.com/show/pKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列选项中,不属于西汉农业发展状况的是()
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
某浮点机字长16位,其浮点数格式为:阶码5位(含1位阶符),采用补码表示,尾数11位(含1位数符),采用补码表示,且尾数为规格化形式。已知X=0.1011000011×20.0101,Y=0.0001100000×20.1000,试求X+Y.要求写出详细的
某DRAM芯片内部存储元排列成1024.×1024的矩阵,且已知其存取周期为0.1μs,最大刷新间隔为2ms。当采用异步刷新方式时,死时间()。
某一个计算机系统采用虚拟页式存储管理方式,当前在处理机上执行的某一个进程的页表如下所示,所有的数字均为十进制,每一项的起始编号是0,并且所有的地址均按字节计址,每页的大小为1024字节。(1)计算下列逻辑地址转换为物理地址,并说明为什么
假定不采用Cache和指令预取技术,且机器处于“开中断”状态,则在下列有关指令执行的叙述中,错误的是____。
下面关于进程的叙述中,正确的是()。
随机试题
有一根导线,每小时通过任一截面积的电量为450库仑,通过导体的电流是()毫安。
A.Aα类纤维B.Aγ类纤维C.B类纤维D.C类纤维支配骨骼肌的运动神经纤维属于
石棉肺的发病机制有以下学说,但最近被多数人认可的是
通过质量控制的动态分析能随时了解生产过程中的质量变化情况,预防出现废品。下列方法中,属于动态分析方法的是()
社区中居民的相互支持及互相帮助,可以满足其在情感和物质上的需要的功能是( )。
制度:管理
有研究者做了个实验,检验游戏对儿童自尊水平的影响,其中游戏是()。
[*]
UniversitiesintheUS Thereare【T1】__________________intheUnitedStates.Nearlyhalfofthe【T2】__________________inAmerica
A、Tochangeajob.B、Toturnthebossdown.C、Tostriketheiron.D、Toaskforaraise.D题目问男士建议女士做什么。女士说想要求老板加薪,但又怕老板拒绝。男士说女士干得
最新回复
(
0
)