一,题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。
二,题目难点在于时间复杂度控制在O(n)
三,方法一
1,分别从数组前,数组后向中间查找。直到前后相遇!!
2,当前得到currentSum>sum说明:大的数太大(数组递增,后面的数太大)。应该将指向最后的标记向前挪动
3,当前得到currentSum<sum说明:大的数太小(数组递增,前面的数太小)。应该将指向最后的标记向后挪动
4,当前得到currentSum=sum说明:找到答案
方法二:假如
1,数组为:a={1、 2、 4、7、11、15 }
2,输入sum=15
3,用15减去a数组中每一个元素得到
b={14、13、11、8、4、0 }
4,a数组向右扫描
b数组向左扫描
5,如果a出现了和b一样的数,稍加判断,就能找出这俩个数来了。
分享到:
相关推荐
本题目要求将一个用户输入的十进制数转换为其对应的二进制表示,并存储在一个数组中。 **代码解析:** 1. **读取输入:** 读取用户输入的十进制数。 ```c printf("请输入一个十进制数\n"); scanf("%d", &decimal...
其基本思想是将数组分为两半,然后比较中间元素与目标值,根据比较结果缩小搜索范围,直到找到目标元素或确定元素不存在。 以下是对程序中关键部分的详细解释: 1. 定义数组s: ```c int s[15]={0,1,2,3,4,5,6,7...
5.6 编写程序,将一个包含有20个数据的数组M分成两个数组:正数数组P和负数数组N,并分别把这两个数组中的数据的个数显示出来。 5.7 试编制一个汇编语言程序,求出首地址为DATA的100D字数组中的最小偶数,并把它放在...
十三、求两个数的最大公约数 =========================================== =========================================== 输出: Test1:比较两个字符串的大小,如: Test2:二维数组获取每一列的最小值...
这段代码通过一系列的除法和取余运算,成功地将输入的数字n分解成了百位、十位与个位三个独立的部分,并存储到了数组a中对应的位置。 #### 2. 输出原始数字及各个位数 ```c printf("the original num:\n"); for (i ...
斐波那契数列的每个数是前两个数的和。我们可以用一维数组存储每个月的兔子数量,根据斐波那契数列的规律填充数组,然后输出结果。 通过这些数组基础题目,学生可以更好地理解数组的性质和操作,为更复杂的编程任务...
(提示: 插入法排序的思路是:先对数组的头两个元素进行排序, 然后根据前两个元素的情况插入第三个元素,再插入第四个元素…)。 (15)爱因斯坦数学题。爱因斯坦曾出过这样一道数学题:有一条长阶梯,若每步跨2...
1、从弹框中,分两次输入两个数字,分别保存在 a 和 b中 2、如果 a 大于 b的话 ,则交换两个数字的位置 使用 短路&&,扩展赋值运算符,位运算 4、条件运算符(三目运算) 单目(一元)运算符 :++,--,! 双目(二元)...
在这个Python基础练习题100例中,我们看到三个具体的题目,分别涉及数组操作、数学计算和逻辑推理。 第一题是关于数字排列的问题。题目要求使用1、2、3、4这四个数字组成互不相同且无重复数字的三位数,并打印所有...
"蛇形数组(数字倒三角)"是一种特殊的矩阵排列方式,通常出现在算法竞赛或编程练习中,例如重庆大学ACM竞赛中的第一题。这个题目要求使用C++编程语言,将数字按照特定的“蛇形”路径填充到一个二维数组中,并将结果...
在这个游戏中,使用了两个数组:`a` 和 `b`。数组 `a` 用于存储计算机生成的四位数,而数组 `b` 则用于存储玩家输入的猜测值。为了确保生成的数字是四位且每位数字不同,有两种方法可以实现: 1. 使用循环和条件...
设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题,这里k不是常量,即它是输入数据的一部分。要求算法的时间复杂性为Θ(n)。 2. 具体要求 输入的第一行是一个正整数m,表示测试...
1. 数组和循环:在第一题中,使用了数组`a[M]`存储用户输入的n个数,并通过两个for循环找出数组中的最大值和最小值。这是对数组操作和循环控制的基本应用。 2. 阶乘函数与条件判断:第二题中,定义了一个名为`fab`...
本资源为第十四届蓝桥杯 Java C 组省赛真题,涵盖了 Java 编程基础知识点,包括结果填空和程序设计两种题型。本总结将对题目中的知识点进行详细说明。 一、结果填空题 结果填空题要求选手根据题目描述直接填写结果...
从给定的文件信息来看,主要涉及到了第14届蓝桥杯C++省赛(初级)的一些真题及其解析。接下来,我们将针对文件中提到的几个知识点进行详细阐述。 ### 完全二叉树的高度 **问题描述:** 设只含根结点的二叉树高度为...
1. **定义过程:**在Form2中定义了过程 `Sub aaa(x, y, z)` 用于计算两个数的平方和,在Module1中定义了过程 `Sub bbb(x, y, z)` 用于计算两个数的立方和。 2. **过程调用:**在Form1的命令按钮Click事件中调用这两...
- 题库中的“friend float max(point& a, point& b)”表示一个友元函数,用于重载max函数,以便比较两个Point对象的大小。 8. 模板 - “template<class T> class f{}”表示定义了一个模板类,模板类可以用来创建...
14. 第十四个试题要求编写一个简单的计算器程序,要求根据用户从键盘输入的表达式,计算并输出结果。这个试题考察了C语言的表达式计算和函数使用。 15. 第十五个试题要求使用时间函数编写一个猜数程序。这个试题...
- 如果当前两个数组区间的长度都为2,则可以确定中位数为这两个区间内较大的数和较小的数。 - 如果`X[aMid] [bMid]`,那么可以断言中位数不会出现在`X`的前半部分或`Y`的后半部分,因此更新`aLeft = aMid`和`...
这份文档是一份C语言习题集合,其中包含多个练习题及其部分答案选项,这些题目涉及了数组的声明、初始化、使用,以及相关指针操作等。下面将详细解释每个知识点。 1. 数组声明与初始化: - 数组声明格式如 `int a...