Tìm cặp gần nhất từ ​​hai mảng đã sắp xếp trong c ++

Giả sử chúng ta có hai mảng đã sắp xếp và một số x, chúng ta phải tìm cặp có tổng gần nhất với x. Và cặp có một phần tử từ mỗi mảng. Chúng ta có hai mảng A1 [0..m-1] và A2 [0..n-1], và một giá trị khác x. Chúng ta phải tìm cặp A1 [i] + A2 [j] sao cho giá trị tuyệt đối của (A1 [i] + A2 [j] - x) là nhỏ nhất. Vì vậy, nếu A1 =[1, 4, 5, 7] và A2 =[10, 20, 30, 40] và x =32, thì đầu ra sẽ là 1 và 30.

Chúng tôi sẽ bắt đầu từ bên trái của A1 và bên phải từ A2, sau đó làm theo các bước sau để tìm cặp như vậy

• Khởi tạo khác biệt, điều này sẽ giữ sự khác biệt giữa cặp và x
• Khởi tạo hai con trỏ trái:=0 và phải:=n - 1
• Trong khi bên trái <=m và bên phải> =0, thực hiện
  • if | A1 [left] + A2 [right] - sum |
  • cập nhật sự khác biệt và kết quả
• if (A1 [left] + A2 [right])
• tăng bên trái 1

Ví dụ

#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);
}

Đầu ra

The closest pair is [1, 30]