Tối đa hóa các cặp duy nhất từ ​​hai mảng trong C ++

Tuyên bố vấn đề

Cho hai mảng có kích thước bằng nhau N, tạo thành số cặp tối đa bằng cách sử dụng các phần tử của chúng, một từ mảng đầu tiên và thứ hai từ mảng thứ hai, sao cho một phần tử từ mỗi mảng được sử dụng nhiều nhất một lần và sự khác biệt tuyệt đối giữa các phần đã chọn các phần tử được sử dụng để tạo thành một cặp nhỏ hơn hoặc bằng một phần tử K.

Ví dụ

Nếu đầu vào là -

arr1 [] ={3, 4, 5, 2, 1}

arr2 [] ={6, 5, 4, 7, 15}

và k =3 thì chúng ta có thể tạo thành 4 cặp sau có hiệu số tuyệt đối nhỏ hơn hoặc bằng 3 -

(1, 4), (2, 5), (3, 6), (4, 7)

Thuật toán

Chúng ta có thể sử dụng phương pháp đệ quy để giải quyết vấn đề này

• Sắp xếp cả hai mảng
• So sánh từng phần tử của mảng đầu tiên với từng phần tử của mảng thứ hai để tìm cặp có thể có, nếu có thể tạo thành một cặp
• Tiếp tục kiểm tra cặp tiếp theo có thể cho phần tử tiếp theo của mảng đầu tiên.

Ví dụ

Bây giờ chúng ta hãy xem một ví dụ -

#include <bits/stdc++.h>
using namespace std;
int getMaxUniquePairs(int *arr1, int *arr2, int n, int k) {
   sort(arr1, arr1 + n);
   sort(arr2, arr2 + n);
   bool visited[n];
   memset(visited, false, sizeof(visited));
   int pairCnt = 0;
   for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
         if (abs(arr1[i] - arr2[j]) <= k &&
         visited[j] == false) {
            ++pairCnt;
            visited[j] = true;
            break;
         }
      }
   }
   return pairCnt;
}
int main() {
   int arr1[] = {3, 4, 5, 2, 1};
   int arr2[] = {6, 5, 4, 7, 15};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int k = 3;
   cout << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
   return 0;
}

Đầu ra

Maximum unique pairs = 4