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