在C ++中从两个排序的数组中找到最接近的对
假设我们有两个排序的数组和一个数字x，我们必须找到总和最接近x的一对。该对中每个数组都有一个元素。我们有两个数组A1[0..m-1]和A2[0..n-1]，以及另一个值x。我们必须找到对A1[i]+A2[j]，使得（A1[i]+A2[j]–x）的绝对值最小。因此，如果A1=[1、4、5、7]，并且A2=[10、20、30、40]，并且x=32，则输出将为1和30。
我们将从A1的左侧开始，从A2的右侧开始，然后按照以下步骤查找这样的对
初始化diff，这将保留对和x之间的差异
初始化两个指针：左：=0和右：=n–1
当左<=m且右>=0时，执行
右移1
向左增加1
更新差异和结果
如果|A1[左]+A2[右]–sum|<diff，然后
如果（A1[左]+A2[右]）<和，则
除此以外
显示结果
示例
#include<iostream>
#include<cmath>
using namespace std;
void findClosestPair(int A1[], int A2[], int m, int n, int x) {
int diff = INT_MAX;
int left_res, right_res;
int left = 0, right = n-1;
while (left<m && right>=0) {
if (abs(A1[left] + A2[right] - x) < diff) {
left_res = left;
right_res = right;
diff = abs(A1[left] + A2[right] - x);
}
if (A1[left] + A2[right] > x)
right--;
else
left++;
}
cout << "The closest pair is [" << A1[left_res] << ", "<< A2[right_res] << "]";
}
int main() {
int ar1[] = {1, 4, 5, 7};
int ar2[] = {10, 20, 30, 40};
int m = sizeof(ar1)/sizeof(ar1[0]);
int n = sizeof(ar2)/sizeof(ar2[0]);
int x = 32;
findClosestPair(ar1, ar2, m, n, x);
}输出结果
The closest pair is [1, 30]
热门推荐
10 给钢琴老师简短祝福语
11 新年祝福语大全牛年 简短
12 家庭恩爱祝福语简短英文
13 疫情对妈妈祝福语简短
14 如何求婚文案祝福语简短
15 优美的春节祝福语简短
16 对好友的祝福语简短
17 职校离校祝福语大全简短
18 给弟弟敬茶祝福语简短