C++에서 정렬된 두 배열에서 가장 가까운 쌍 찾기

두 개의 정렬된 배열과 숫자 x가 있다고 가정하면 합이 x에 가장 가까운 쌍을 찾아야 합니다. 그리고 쌍에는 각 배열의 요소가 있습니다. 두 개의 배열 A1 [0..m-1]과 A2 [0..n-1]와 또 다른 값 x가 있습니다. (A1[i] + A2[j] – x)의 절대값이 최소가 되도록 A1[i] + A2[j] 쌍을 찾아야 합니다. 따라서 A1 =[1, 4, 5, 7]이고 A2 =[10, 20, 30, 40] 및 x =32이면 출력은 1과 30이 됩니다.

A1의 왼쪽부터 A2의 오른쪽부터 시작하여 다음 단계에 따라 해당 쌍을 찾습니다.

• diff를 초기화하면 pair와 x의 차이가 유지됩니다.
• 두 포인터 초기화 왼쪽 :=0 및 오른쪽 :=n – 1
• 왼쪽 <=m, 오른쪽>=0인 동안 do
  • if |A1[왼쪽] + A2[오른쪽] – 합계| <차이, 그럼
    • 차이 및 결과 업데이트
  • if (A1[left] + A2[right])
  • 왼쪽으로 1 증가
• 그렇지 않으면
  • 오른쪽으로 1 감소

예시

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