# 從兩個數組最大化唯一對 > 原文： [https://www.geeksforgeeks.org/maximizing-unique-pairs-two-arrays/](https://www.geeksforgeeks.org/maximizing-unique-pairs-two-arrays/) 給定兩個大小為 N 的數組，使用它們的元素形成最大對數，一個元素來自第一個數組，第二個元素來自第二個數組，這樣每個數組中的元素最多使用一次，并且所選元素之間的絕對差 用于形成一對的元素小于或等于給定元素 K。 **示例**： ``` Input : a[] = {3, 4, 5, 2, 1} b[] = {6, 5, 4, 7, 15} k = 3 Output : 4 The maximum number of pairs that can be formed using the above 2 arrays is 4 and the corresponding pairs are [1, 4], [2, 5], [3, 6], [4, 7], we can't pair the remaining elements. Other way of pairing under given constraint is [2, 5], [3, 6], [4, 4], but count of pairs here is 3 which is less than the result 4. ``` **簡單方法**：通過舉幾個例子，我們可以觀察到如果對兩個數組都進行排序。 然后，通過為每個元素選擇最接近的可行元素，我們得到最佳答案。 在這種方法中，我們首先對兩個數組都進行排序，然后將第一個數組中的每個元素與第二個數組中的每個元素比較可能的一對，如果有可能形成一對，我們就組成該對并檢查下一個可能的對 配對第一個數組的下一個元素。 ## C++ ```cpp // C++ implementation of above approach #include <bits/stdc++.h> #define ll long long int using namespace std; // Returns count of maximum pairs that caan // be formed from a[] and b[] under given // constraints. ll findMaxPairs(ll a[], ll b[], ll n, ll k) { ????sort(a, a+n); // Sorting the first array. ????sort(b, b+n); // Sorting the second array. ????// To keep track of visited elements of b[] ????bool flag[n]; ????memset(flag, false, sizeof(flag)); ????// For every element of a[], find a pair ????// for it and break as soon as a pair is ????// found. ????int result = 0; ????for (int i=0; i<n; i++) ????{ ????????for (int j=0; j<n; j++) ????????{ ????????????if (abs(a[i]-b[j])<=k && flag[j]==false) ????????????{ ????????????????// Increasing the count if a pair is formed. ????????????????result++; ????????????????/* Making the corresponding flag array ???????????????????element as 1 indicating the element ???????????????????in the second array element has ???????????????????been used. */ ????????????????flag[j] = true; ????????????????// We break the loop to make sure an ????????????????// element of a[] is used only once. ????????????????break; ????????????} ????????} ????} ????return result; } // Driver code int main() { ????ll a[] = {10, 15, 20}, b[] = {17, 12, 24}; ????int n = sizeof(a)/sizeof(a[0]); ????int k = 3; ????cout << findMaxPairs(a, b, n, k); ????return 0; } ``` ## Java ```java // Java implementation of above approach import java.util.*; class solution { // Returns count of maximum pairs that caan // be formed from a[] and b[] under given // constraints. static int findMaxPairs(int a[], int b[], int n, int k) { ????Arrays.sort(a); // Sorting the first array. ????Arrays.sort(b); // Sorting the second array. ????// To keep track of visited elements of b[] ????boolean []flag = new boolean[n]; ????Arrays.fill(flag,false); ????// For every element of a[], find a pair ????// for it and break as soon as a pair is ????// found. ????int result = 0; ????for (int i=0; i<n; i++) ????{ ????????for (int j=0; j<n; j++) ????????{ ????????????if (Math.abs(a[i]-b[j])<=k && flag[j]==false) ????????????{ ????????????????// Increasing the count if a pair is formed. ????????????????result++; ????????????????/* Making the corresponding flag array ????????????????element as 1 indicating the element ????????????????in the second array element has ????????????????been used. */ ????????????????flag[j] = true; ????????????????// We break the loop to make sure an ????????????????// element of a[] is used only once. ????????????????break; ????????????} ????????} ????} ????return result; } // Driver code public static void main(String args[]) { ????int[] a = {10, 15, 20}; ????int[] b = {17, 12, 24}; ????int n = a.length; ????int k = 3; ????System.out.println(findMaxPairs(a, b, n, k)); } } // This code is contributed by // Shashank_Sharma ``` ## Python 3 ``` # Returns count of maximum pairs? # that can be formed from a[] and? # b[] under given constraints. def findMaxPairs(a, b, n, k): ????a.sort() # Sorting the first array. ????b.sort() # Sorting the second array. ????# To keep track of visited ????# elements of b[] ????flag = [False] * n ????# For every element of a[], find? ????# a pair for it and break as soon? ????# as a pair is found. ????result = 0 ????for i in range(n): ????????for j in range(n): ????????????if (abs(a[i] - b[j]) <= k and? ?????????????????????????flag[j] == False): ????????????????# Increasing the count if? ????????????????# a pair is formed. ????????????????result += 1 ????????????????''' Making the corresponding flag array ????????????????element as 1 indicating the element ????????????????in the second array element has ????????????????been used. ''' ????????????????flag[j] = True ????????????????# We break the loop to make sure an ????????????????# element of a[] is used only once. ????????????????break ????return result # Driver code if __name__ == "__main__": ????a = [10, 15, 20] ????b = [17, 12, 24] ????n = len(a) ????k = 3 ????print(findMaxPairs(a, b, n, k)) # This code is contributed # by ChitraNayal ``` ## C# ```cs // C# implementation of above approach using System;? class GFG? {? ????// Returns count of maximum pairs that caan? ????// be formed from a[] and b[] under given? ????// constraints.? ????static int findMaxPairs(int []a, int []b,? ????????????????????????????????int n, int k)? ????{? ????????Array.Sort(a); // Sorting the first array.? ????????Array.Sort(b); // Sorting the second array.? ????????// To keep track of visited elements of b[]? ????????bool []flag = new bool[n];? ????????//Arrays.fill(flag,false);? ????????// For every element of a[], find a pair? ????????// for it and break as soon as a pair is? ????????// found.? ????????int result = 0;? ????????for (int i = 0; i < n; i++)? ????????{? ????????????for (int j = 0; j < n; j++)? ????????????{? ????????????????if (Math.Abs(a[i] - b[j]) <= k && flag[j] == false)? ????????????????{? ????????????????????// Increasing the count if a pair is formed.? ????????????????????result++;? ????????????????????/* Making the corresponding flag array? ????????????????????element as 1 indicating the element? ????????????????????in the second array element has? ????????????????????been used. */ ????????????????????flag[j] = true;? ????????????????????// We break the loop to make sure an? ????????????????????// element of a[] is used only once.? ????????????????????break;? ????????????????}? ????????????}? ????????}? ????????return result;? ????}? ????// Driver code? ????public static void Main()? ????{? ????????int[] a = {10, 15, 20};? ????????int[] b = {17, 12, 24};? ????????int n = a.Length;? ????????int k = 3;? ????????Console.WriteLine(findMaxPairs(a, b, n, k));? ????}? }? // This code is contributed by Rajput-Ji ``` **輸出**： ``` 2 ``` **時間復雜度**： `O(n^2)` **輔助空間**：`O(n)` **高效方法**：在這種方法中，我們不檢查所有可能的對組合，而是通過使用 2 指針方法僅檢查對的可行組合來優化代碼。 ## C++ ``` #include <bits/stdc++.h> #define ll long long int using namespace std; // Returns count of maximum pairs that caan // be formed from a[] and b[] under given // constraints. ll findMaxPairs(ll a[], ll b[], ll n, ll k) { ????sort(a, a+n); // Sorting the first array. ????sort(b, b+n); // Sorting the second array. ????int result = 0; ????for (int i=0, j=0; i<n && j<n;) ????{ ????????if (abs(a[i] - b[j]) <= k) ????????{ ????????????result++; ????????????// Increasing array pointer of ????????????// both the first and the second array. ????????????i++; ????????????j++; ????????} ????????// Increasing array pointer of the second array. ????????else if(a[i] > b[j]) ????????????j++; ????????// Increasing array pointer of the first array. ????????else ????????????i++; ????} ????return result; } // Driver code int main() { ????ll a[] = {10, 15, 20}; ????ll b[] = {17, 12, 24}; ????int n = sizeof(a)/sizeof(a[0]); ????int k = 3; ????cout << findMaxPairs(a, b, n, k); ????return 0; } ``` ## Java ```java // Java program for Maximizing Unique Pairs? // from two arrays import java.util.*; class GFG { // Returns count of maximum pairs that caan // be formed from a[] and b[] under given // constraints. static int findMaxPairs(int a[], int b[],? ????????????????????????int n, int k) { ????Arrays.sort(a); // Sorting the first array. ????Arrays.sort(b); // Sorting the second array. ????int result = 0; ????for (int i = 0, j = 0; i < n && j < n;) ????{ ????????if (Math.abs(a[i] - b[j]) <= k) ????????{ ????????????result++; ????????????// Increasing array pointer of ????????????// both the first and the second array. ????????????i++; ????????????j++; ????????} ????????// Increasing array pointer? ????????// of the second array. ????????else if(a[i] > b[j]) ????????????j++; ????????// Increasing array pointer? ????????// of the first array. ????????else ????????????i++; ????} ????return result; } // Driver code public static void main(String args[]) { ????int a[] = {10, 15, 20}; ????int b[] = {17, 12, 24}; ????int n = a.length; ????int k = 3; ????System.out.println(findMaxPairs(a, b, n, k)); } } // This code is contributed by // Sanjit_Prasad ``` ## Python3 ```py # Python3 program for # Maximizing Unique Pairs? # from two arrays # Returns count of maximum pairs that caan? # be formed from a[] and b[] under given? # constraints.? def findMaxPairs(a,b,n,k): ????# Sorting the first array. ????a.sort() ????# Sorting the second array. ????b.sort()? ????result =0 ????j=0 ????for i in range(n): ????????if j<n: ????????????if abs(a[i]-b[j])<=k: ????????????????result+=1 ????????????# Increasing array pointer of? ????????????# both the first and the second array.? ????????????????j +=1 ????????????# Increasing array pointer of? ????????????# the second array.? ????????????elif a[i]>b[j]: ????????????????j+=1 ????return result # Driver code if __name__=='__main__': ????a = [10,15,20] ????b = [17,12,24] ????n = len(a) ????k =3 ????print(findMaxPairs(a,b,n,k)) # This code is contributed by? # Shrikant13 ``` ## C# ``` // C# program for Maximizing Unique Pairs? // from two arrays using System; class GFG { // Returns count of maximum pairs that caan // be formed from a[] and b[] under given // constraints. static int findMaxPairs(int []a, int []b,? ????????????????????????int n, int k) { ????Array.Sort(a); // Sorting the first array. ????Array.Sort(b); // Sorting the second array. ????int result = 0; ????for (int i = 0, j = 0; i < n && j < n;) ????{ ????????if (Math.Abs(a[i] - b[j]) <= k) ????????{ ????????????result++; ????????????// Increasing array pointer of ????????????// both the first and the second array. ????????????i++; ????????????j++; ????????} ????????// Increasing array pointer? ????????// of the second array. ????????else if(a[i] > b[j]) ????????????j++; ????????// Increasing array pointer? ????????// of the first array. ????????else ????????????i++; ????} ????return result; } // Driver code public static void Main(String []args) { ????int []a = {10, 15, 20}; ????int []b = {17, 12, 24}; ????int n = a.Length; ????int k = 3; ????Console.WriteLine(findMaxPairs(a, b, n, k)); } } // This code has been contributed by 29AjayKumar ``` **輸出**： ``` 2 ``` **時間復雜度**：`O(N log N)` **輔助空間**：`O(1)` 本文由 [**Aditya Gupta**](https://www.linkedin.com/in/aditya-gupta-437504a7?trk=hp-identity-name) 提供。 如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。 查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。