首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一个含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
47
问题
给定一个含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
学硕统考专业
相关试题推荐
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数;(2)画出散列表;
以下关于CPU的叙述中,错误的是()。
假设有一个进程拥有两个线程(编号为0和1)需要去访问同一个共享资源,为了避免竞争状态的问题,必须实现一种互斥机制,使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码:intflagL22;/*flag数组,初始化为FALSE*/
随机试题
在大地测量中,对于平均海水面即基准面以下的地面点,其高程用从平均海平面向下量的负高程表示,如水面下某点距平均海平面的竖直距离为12m,则标为-12.0m。水下地形用连接相同水深点的等深线表示,形成()。
隧道照明控制系统能根据交通量的变化及()对洞内照明强度进行调节。
根据以下资料,回答下列问题。两周就诊率被定义为每百人中两周内因病或身体不适寻求各级医疗机构治疗服务的人次数。第五次国家卫生服务调查结果显示,调查地区居民两周就诊率为13.0%,其中城市地区为13.3%,农村地区为12.8%。城市地区,东部、中部、
一辆客车、一辆货车和一辆小轿车在同一条直线上朝同一方向行驶,在某一时刻,货车在中,客车在前,小轿车在后,且它们的距离相等。走了10分钟,小轿车追上了货车;又走了5分钟,小轿车追上了客车。问再过多少分钟,货车将追上客车?()
根据下面材料回答下列问题。2015年一季度,A省商品房销售面积1175.2万平方米,下降13.4%,降幅比1—2月收窄13.8个百分点。其中,商品住宅销售面积1036.3万平方米,下降15%;办公楼销售面积15.2万平方米,下降48.7%;商业营业用房销
Completethenotesbelow.WriteNOMORETHANTWOWORDSforeachanswer.ChainStoresintheUKInitialexpansionThecompanye
Herushedintotheclassroom_______withtearsonhisface.(anger)
Directions:Inthispart,youwillhave15minutestogooverthepassagequicklyandanswerthequestionsonAnswerSheet1.Fo
Theboyslippedoutoftheroomandheadedfortheswimmingpoolwithouthisparents’__________.
TheincreasingAmericanizationofJapaneselifeisevidentinmanyways.Onesuchwayisthegrowingpopularityofcreditcards.
最新回复
(
0
)