给定两个大小相同的数组N，使用它们的元素形成最大数量的对，一个来自第一个数组，第二个来自第二个数组，这样每个数组中的元素最多使用一次，用于形成对的选定元素之间的绝对差小于或等于给定元素K。 例如：
null
Input : a[] = {3, 4, 5, 2, 1} b[] = {6, 5, 4, 7, 15} k = 3Output : 4The maximum number of pairs that can be formedusing the above 2 arrays is 4 and the correspondingpairs 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 hereis 3 which is less than the result 4.
简单方法： 通过几个例子，我们可以观察到，如果我们对两个数组进行排序。然后，通过为每个元素选择最接近的可行元素，我们得到了最佳答案。 在这种方法中，我们首先对两个数组进行排序，然后将第一个数组的每个元素与第二个数组的每个元素进行比较，寻找可能的对。如果可能形成对，我们就形成对，然后检查第一个数组的下一个元素的下一个可能的对。
C++
// C++ implementation of above approach #include <bits/stdc++.h> #define ll long long int using namespace std; // Returns count of maximum pairs that can // 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 implementation of above approach import java.util.*; class solution { // Returns count of maximum pairs that can // 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#
// C# implementation of above approach using System; class GFG { // Returns count of maximum pairs that can // 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 |
Javascript
<script> // Javascript implementation of above approach // Returns count of maximum pairs that can // be formed from a[] and b[] under given // constraints. function findMaxPairs(a,b,n,k) { a.sort( function (c,d){ return c-d;}); // Sorting the first array. b.sort( function (c,d){ return c-d;}) // Sorting the second array. // To keep track of visited elements of b[] let flag = new Array(n); for (let i=0;i<flag.length;i++) { flag[i]= false ; } // For every element of a[], find a pair // for it and break as soon as a pair is // found. let result = 0; for (let i=0; i<n; i++) { for (let 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 let a=[10, 15, 20]; let b=[17, 12, 24]; let n = a.length; let k = 3; document.write(findMaxPairs(a, b, n, k)); // This code is contributed by rag2127 </script> |
输出：
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 can // 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 program for Maximizing Unique Pairs // from two arrays import java.util.*; class GFG { // Returns count of maximum pairs that can // 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
# Python3 program for # Maximizing Unique Pairs # from two arrays # Returns count of maximum pairs that can # 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 can // 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 |
Javascript
<script> // Javascript program for Maximizing // Unique Pairs from two arrays // Returns count of maximum pairs that can // be formed from a[] and b[] under given // constraints. function findMaxPairs(a, b, n, k) { // Sorting the first array. a.sort( function (a, b){ return a - b}); // Sorting the second array. b.sort( function (a, b){ return a - b}); let result = 0; for (let 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; } let a = [10, 15, 20]; let b = [17, 12, 24]; let n = a.length; let k = 3; document.write(findMaxPairs(a, b, n, k)); </script> |
输出：
2
时间复杂性： O（n日志n） 辅助空间： O（1） 本文由 阿迪蒂亚·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
