ค้นหาคู่ที่ใกล้เคียงที่สุดจากสองอาร์เรย์ที่เรียงลำดับใน 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
• ในขณะที่ซ้าย <=ม. และ ขวา>=0, ทำ
  • ถ้า |A1[ซ้าย] + A2[ขวา] – ผลรวม| <แตกต่าง แล้วก็
    • อัปเดตส่วนต่างและผลลัพธ์
  • ถ้า (A1[ซ้าย] + A2[ขวา]) <ผลรวม แล้ว
    • เพิ่มขึ้นทางซ้าย 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]