/*
* 找一对数
*
* 例题1：
* 输入 n(n<100,000)个整数，找出其中的两个数，他们之和等于整数 m
* (假定肯定有解)。题中所有的整数能用 int 表示。
*
* 解法：
* 1) 将数组排序，复杂度是 O(n * log(n))。
* 2) 查找时，设置两个变量 i 和 j，i=0, j=n-1; 如果 a[i]+a[j] > m
* j-1，小于则 i+1， 直至a[i]+a[j] = m，复杂度 O(n)。
*
**/
#include <stdio.h>
#define <stdlib.h>
int main(void)
{
// 读入数据
int m;
scanf("%d", &m);
int n;
scanf("%d", &n);
int *arr = (int *)malloc(sizeof(int) * n);
for (int i=0; i<n; i++){
scanf("%d", &arr[i]);
}
// 排序
qsort(arr, n, sizeof(int), Compare);
// 查找符合条件的两个数
int i = 0, j = n-1;
while (arr[i] + arr[j] != m){
if (arr[i] + arr[j] > m){
j--;
} else {
i++;
}
}
printf("%d + %d = %d", arr[i], arr[j], m);
}
找一对数
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 【蝴蝶效应】 蝴蝶效应:上个世纪70年代，美国一个名叫洛伦兹的气象学家在解释空气系统理论时说，亚马逊雨林一只蝴蝶...
