在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]