首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一个含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
44
问题
给定一个含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
学硕统考专业
相关试题推荐
严复翻译的《天演论》一书的出版时间是()。
《中国国民党改组宣言》发表的时间是()。
系统阐明社会主义初级阶段理论是在()。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
既考虑作业等待时间又考虑作业执行时间的调度算法是()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数;(2)画出散列表;
随机试题
消毒不耐热、不耐湿的物品宜使用
患者,女,55岁。患下颌骨恶性肿物,进行性张口困难,下唇麻木。出现这些症状的可能原因为
活塞一个行程,曲轴旋转()周。
资产支持证券就是由()发行的、代表特定目的的信托的信托受益权份额。
根据中国证监会对基金类别的分类标准,()以上的基金资产投资于股票的为要基金。
董事会处在声誉风险管理的第一线,应当随时了解各类利益持有者所关注的问题,并且正确预测其对商业银行的业务、政策或运营调整可能产生的反应。()
在上文横线上填入相关词语,顺序正确的一组是()。在[a]、[b]、[c]处恰当的措辞是()。
SQLServer2000除了具有DBMS的基本功能特点外,还具有许多功能特点。下列哪一个不是SQLServer2000的功能特点?
Darwinproposedthetheoryofsexualselectiontoexplaintheoriginofostentatiousplumageincertainbirdspecies,mai
Nexttimeyouenterausernameandpassword,thinkabouttherhythmofyourtyping.Notonlycanitbeusedtoidentifyyou,it
最新回复
(
0
)