输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们

admin2014-04-17 61

问题输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：
说明你所设计算法的时间复杂度。

选项

答案时间复杂度分析：在while的循环中，每次根据curSum和sum之间的大小关系来决定是改变ahead还是改变behind。这个过程每次是O(1)的。在整个算法流程中，因为ahead始终大于behind，如果一个数被ahead扫过了，那么它不会被behind扫到，也不会被ahead再次扫到；同样的，如果一个数被behind扫过了，那么它将不会再被ahead或者behind扫到。所以循环最多执行n—1次就会结束，故整个算法的时间复杂度为O(n)。

解析

转载请注明原文地址:https://kaotiyun.com/show/iYxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

日本推行锁国体制的原因及影响。

1971年9月美苏英法四国签署()，肯定了西柏林的占领制度，柏林问题得以解决。

毛泽东从事了大量理论研究工作，系统阐述了新民主主义的理论，下列选项中，不属于这一范围的是()

“瓜步之战”发生在下列哪两个政权之间?()

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

If_____,theexperimentwillbesuccessful.

患者，男性，46岁。因呕吐、腹泻、低热于门诊应用庆大霉素32万U／日，共治疗5天，近日来觉尿量有所减少，约700～800ml／24h，伴乏力、头晕。检查尿蛋白(+)，Hb100g／L，血清钾6．5mmol／L，BUN33．5mmol／L，血肌酐884／mm

减轻风心病心衰时心脏后负荷减轻风心病心衰时心脏前负荷

典型溃疡性结肠炎患者粪便的特点是

施工中采用IC卡实名制管理可实现()等管理功能。

下列有关政府信息公开制度的说法中符合《政府信息公开条例》规定的有()。

文言文中的倒装句主要分为四类：_____、宾语前置、_、_____。

简述法的概念及其基本特征。

下列选项表述正确的是()。

A、Theyarenewerthantheformationsinmostcaves.B、Theywereformedbysulfuricacid.C、Theyhavebeenartificiallypreserved

计算机408

学硕统考专业

日本推行锁国体制的原因及影响。

1971年9月美苏英法四国签署()，肯定了西柏林的占领制度，柏林问题得以解决。

毛泽东从事了大量理论研究工作，系统阐述了新民主主义的理论，下列选项中，不属于这一范围的是()

“瓜步之战”发生在下列哪两个政权之间?()

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是()，最多需要比较的次数是()。

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

If_____,theexperimentwillbesuccessful.

患者，男性，46岁。因呕吐、腹泻、低热于门诊应用庆大霉素32万U／日，共治疗5天，近日来觉尿量有所减少，约700～800ml／24h，伴乏力、头晕。检查尿蛋白(+)，Hb100g／L，血清钾6．5mmol／L，BUN33．5mmol／L，血肌酐884／mm

减轻风心病心衰时心脏后负荷减轻风心病心衰时心脏前负荷

典型溃疡性结肠炎患者粪便的特点是

施工中采用IC卡实名制管理可实现()等管理功能。

下列有关政府信息公开制度的说法中符合《政府信息公开条例》规定的有()。

文言文中的倒装句主要分为四类：_________、宾语前置、_________、_________。

简述法的概念及其基本特征。

下列选项表述正确的是()。

A、Theyarenewerthantheformationsinmostcaves.B、Theywereformedbysulfuricacid.C、Theyhavebeenartificiallypreserved

文言文中的倒装句主要分为四类：_____、宾语前置、_、_____。