首页 > 代码库 > 023 和为S的两个数字(keep it up)
023 和为S的两个数字(keep it up)
- 题目描述:
- 输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
- 输入:
- 每个测试案例包括两行:第一行包含一个整数n和k,n表示数组中的元素个数,k表示两数之和。其中1 <= n <= 10^6,k为int第二行包含n个整数,每个数组均为int类型。
- 输出:
- 对应每个测试案例,输出两个数,小的先输出。如果找不到,则输出“-1 -1”
- 样例输入:
6 15 1 2 4 7 11 15
- 样例输出:
4 11
题目中输入的数据时有序递增的,而且是找两个数,很快想到快速排序的算法,一般这种有序的数都可以借鉴排序算法(三个while循环):
1首先我们判断array[low] + array[height] < k,那么low就一直加1,并且保证low < height
2然后判断array[low]+array[height] > k,那么height就一直减1,并且保证 low < height
3判段 array[low] + array[height] == k,等于就返回1,表示找到了,否则继续
呵呵,是不是和快排的思想一样。
下面是代码:
#include <stdio.h> #include <stdlib.h> #define MaxSize 1000000 int Array[MaxSize]; int findMinTwoNumber(int vK, int vN, int *vLeft, int *vRight) { if (vN < 2) return 0; int Low, Hight; Low = 0; Hight = vN-1; while (Low < Hight) { while (Array[Low] + Array[Hight] < vK && Low < Hight) ++Low; while (Array[Low] + Array[Hight] > vK && Low < Hight) --Hight; if (Array[Low] + Array[Hight] == vK && Low < Hight) { *vLeft = Low; *vRight = Hight; return 1; } } return 0; } int main() { int K, N, i, Ret, Left, Right; while (scanf("%d %d", &N, &K) != EOF) { for (i = 0; i < N; ++i) { scanf("%d", &Array[i]); } Ret = findMinTwoNumber(K, N, &Left, &Right); if (Ret) { printf("%d %d\n", Array[Left], Array[Right]); } else { printf("-1 -1\n"); } } //system("pause"); return 0; }http://blog.csdn.net/xiaoliangsky/article/details/40901373
http://ac.jobdu.com/problem.php?pid=1352
023 和为S的两个数字(keep it up)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。