หาคู่ที่ใกล้เคียงที่สุดจากสอง Sorted Arrays ใน C++

สมมติว่ามี Sorted Arrays สองอัน และตัวเลข 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 แล้วทำตามขั้นตอน:

• Initialize diff เก็บความต่างระหว่างคู่กับ x
• Initialize left := 0 และ right := n-1
• While left < m และ right >= 0:
  • ถ้า |A1[left] + A2[right] - sum| < diff อัปเดต diff และผลลัพธ์
  • ถ้า (A1[left] + A2[right]) < sum เพิ่ม left 1
  • มิฉะนั้น ลด right 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]