给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法...

问答题 给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5，3，2，3}中未出现的最小正整数是1；数组{1，2，3}中未出现的最小正整数是4。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。

参考答案：1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n...

点击查看完整答案

你可能感兴趣的试题

1.单项选择题减法指令“sub R1，R2，R3”的功能为“（R1）-（R2）→ R3”，该指令执行后将生成进位/借位标志CF和溢出标志OF。若（R1）= FFFF FFFFH，（R2）= FFFF FFF0H，则该减法指令执行后，CF与OF分别为（）

A.CF=0，OF=0
B.CF=1，OF=0
C.CF=0，0F=1
D CF=1，OF=1

点击查看答案

2.单项选择题无需转换即可由SMTP协议直接传输的内容是（）

A.JPEG图像
B.MPEG视频
C.EXE文件
D.ASCII文本

点击查看答案

3.单项选择题UDP协议实现分用（demultiplexing）时所依据的头部字段是（）

A.源端口号
B.目的端口号
C.长度
D.校验和

点击查看答案

4.单项选择题某路由表中有转发接口相同的4条路由表项，其目的网络地址分别为35.230.32.0/21、35.230.40.0/21、35.230.48.0/21和35.230.56.0/21，将该4条路由聚合后的目的网络地址为（）

A.35.230.0.0/19
B.35.230.0.0/20
C.35.230.32.0/19
D.35.230.32.0/20

点击查看答案

5.单项选择题 路由器R通过以太网交换机S1和S2连接两个网络，R的接口、主机H1和H2的IP地址与MAC地址如下图所示。若H1向H2发送1个IP分组P，则H1发出的封装P的以太网帧的目的MAC地址、H2收到的封装P的以太网帧的源MAC地址分别是（）

A.00-a1-b2-c3-d4-62、00-1a-2b-3c-4d-52
B.00-a1-b2-c3-d4-62、00-a1-b2-c3-d4-61
C.00-1a-2b-3c-4d-51、00-1a-2b-3c-4d-52
D.00-1a-2b-3c-4d-51、00-a1-b2-c3-d4-61

点击查看答案

6.单项选择题主机甲采用停-等协议向主机乙发送数据，数据传输速率是3kbps，单向传播延时是200ms，忽略确认帧的传输延时。当信道利用率等于40%时，数据帧的长度为（）

A.240比特
B.400比特
C.480比特
D.800比特

点击查看答案

7.单项选择题IEEE 802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是（）

A.发送确认帧
B.采用二进制指数退避
C.使用多个MAC地址
D.交换RTS与CTS帧

点击查看答案

8.单项选择题下列选项中，不属于物理层接口规范定义范畴的是（）

A.接口形状
B.引脚功能
C.物理地址
D.信号电平

点击查看答案

9.单项选择题下列TCP/IP应用层协议中，可以使用传输层无连接服务的是（）

A.FTP
B.DNS
C.SMTP
D.HTTP