两个数组的K个最大和组合-yiteyi-C++库

给定两个大小相同的数组（A、B）和N（两个数组的大小）。 A. 和组合 通过将数组A中的一个元素与数组B中的另一个元素相加来实现。显示 最大K个有效和组合 从所有可能的和组合中。

null

例如：

Input :  A[] : {3, 2}          B[] : {1, 4}         K : 2 [Number of maximum sum               combinations to be printed]Output : 7    // (A : 3) + (B : 4)         6    // (A : 2) + (B : 4)Input :  A[] : {4, 2, 5, 1}         B[] : {8, 0, 3, 5}         K : 3Output : 13   // (A : 5) + (B : 8)         12   // (A : 4) + (B :  8)         10   // (A : 2) + (B : 8)

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法1（朴素算法）： 我们可以通过从数组A中提取一个元素，从数组B中提取另一个元素，并将它们插入到最大堆中，来使用蛮力进行所有可能的组合。在max-heap中，最大元素位于根节点，因此每当我们从max-heap弹出时，我们都会得到堆中存在的最大元素。插入所有和组合后，我们从最大堆中取出K个元素并显示它。以下是上述方法的实施情况。

C++

                         // A simple C++ program to find N maximum                       
                         // combinations from two arrays,                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to display first N maximum sum                       
                         // combinations                       
                         void                                     KMaxCombinations(                                     int                                     A[],                                     int                                     B[],                       
                                                 int                                     N,                                     int                                     K)                       
                         {                       
                                                 // max heap.                       
                                                 priority_queue<                                     int                                     > pq;                       
           
                                                 // insert all the possible combinations                       
                                                 // in max heap.                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++)                       
                                                 for                                     (                                     int                                     j = 0; j < N; j++)                       
                                                 pq.push(A[i] + B[j]);                       
           
                                                 // pop first N elements from max heap                       
                                                 // and display them.                       
                                                 int                                     count = 0;                       
                                                 while                                     (count < K) {                       
                                                 cout << pq.top() << endl;                       
                                                 pq.pop();                       
                                                 count++;                       
                                                 }                       
                         }                       
           
                         // Driver Code.                       
                         int                                     main()                       
                         {                       
                                                 int                                     A[] = { 4, 2, 5, 1 };                       
                                                 int                                     B[] = { 8, 0, 5, 3 };                       
                                                 int                                     N =                                     sizeof                                     (A) /                                     sizeof                                     (A[0]);                       
                                                 int                                     K = 3;                       
                                   
                                                 // Function call                       
                                                 KMaxCombinations(A, B, N, K);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find K                       
                         // maximum combinations                       
                         // from two arrays,                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 // function to display first K                       
                                                 // maximum sum combinations                       
                                                 static                                     void                                     KMaxCombinations(                                     int                                     A[],                                     int                                     B[],                       
                                                 int                                     N,                                     int                                     K)                       
                                                 {                       
                                                 // max heap.                       
                                                 PriorityQueue<Integer> pq                       
                                                 =                                     new                                     PriorityQueue<Integer>(                       
                                                 Collections.reverseOrder());                       
           
                                                 // Insert all the possible                       
                                                 // combinations in max heap.                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < N; i++)                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < N; j++)                       
                                                 pq.add(A[i] + B[j]);                       
           
                                                 // Pop first N elements                       
                                                 // from max heap and                       
                                                 // display them.                       
                                                 int                                     count =                                     0                                     ;                       
           
                                                 while                                     (count < K) {                       
                                                 System.out.println(pq.peek());                       
                                                 pq.remove();                       
                                                 count++;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     A[] = {                                     4                                     ,                                     2                                     ,                                     5                                     ,                                     1                                     };                       
                                                 int                                     B[] = {                                     8                                     ,                                     0                                     ,                                     5                                     ,                                     3                                     };                       
                                                 int                                     N = A.length;                       
                                                 int                                     K =                                     3                                     ;                       
           
                                                 // Function Call                       
                                                 KMaxCombinations(A, B, N, K);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Mayank Tyagi                       

Python 3

                         # Python program to find                       
                         # K maximum combinations                       
                         # from two arrays                       
                         import                                     math                       
                         from                                     queue                                     import                                     PriorityQueue                       
           
                         # Function to display first K                       
                         # maximum sum combinations                       
           
           
                         def                                     KMaxCombinations(A, B, N, K):                       
           
                                                 # Max heap.                       
                                                 pq                                     =                                     PriorityQueue()                       
           
                                                 # Insert all the possible                       
                                                 # combinations in max heap.                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , N):                       
                                                 for                                     j                                     in                                     range                                     (                                     0                                     , N):                       
                                                 a                                     =                                     A[i]                                     +                                     B[j]                       
                                                 pq.put((                                     -                                     a, a))                       
           
                                                 # Pop first N elements from                       
                                                 # max heap and display them.                       
                                                 count                                     =                                     0                       
                                                 while                                     (count < K):                       
                                                 print                                     (pq.get()[                                     1                                     ])                       
                                                 count                                     =                                     count                                     +                                     1                       
           
           
                         # Driver method                       
                         A                                     =                                     [                                     4                                     ,                                     2                                     ,                                     5                                     ,                                     1                                     ]                       
                         B                                     =                                     [                                     8                                     ,                                     0                                     ,                                     5                                     ,                                     3                                     ]                       
                         N                                     =                                     len                                     (A)                       
                         K                                     =                                     3                       
           
                         # Function call                       
                         KMaxCombinations(A, B, N, K)                       
           
                         # This code is contributed                       
                         # by Gitanjali.                       

C#

                         // C# program to find K                       
                         // maximum combinations                       
                         // from two arrays,                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         public                                     class                                     GFG                       
                         {                       
           
                                                 // function to display first K                       
                                                 // maximum sum combinations                       
                                                 static                                     void                                     KMaxCombinations(                                     int                                     []A,                                     int                                     []B,                       
                                                 int                                     N,                                     int                                     K)                       
                                                 {                       
           
                                                 // max heap.                       
                                                 List<                                     int                                     > pq                       
                                                 =                                     new                                     List<                                     int                                     >();                       
           
                                                 // Insert all the possible                       
                                                 // combinations in max heap.                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++)                       
                                                 for                                     (                                     int                                     j = 0; j < N; j++)                       
                                                 pq.Add(A[i] + B[j]);                       
           
                                                 // Pop first N elements                       
                                                 // from max heap and                       
                                                 // display them.                       
                                                 int                                     count = 0;                       
                                                 pq.Sort();                       
                                                 pq.Reverse();                       
                                                 while                                     (count < K)                       
                                                 {                       
                                                 Console.WriteLine(pq[0]);                       
                                                 pq.RemoveAt(0);                       
                                                 count++;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     []A = { 4, 2, 5, 1 };                       
                                                 int                                     []B = { 8, 0, 5, 3 };                       
                                                 int                                     N = A.Length;                       
                                                 int                                     K = 3;                       
           
                                                 // Function Call                       
                                                 KMaxCombinations(A, B, N, K);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

Javascript

                         <script>                       
                         // Javascript program to find K                       
                         // maximum combinations                       
                         // from two arrays,                       
           
                         // function to display first K                       
                         // maximum sum combinations                       
                         function                                     KMaxCombinations(A, B, N, K)                       
                         {                       
           
                                                 // max heap.                       
                                                 let pq = [];                       
           
                                                 // Insert all the possible                       
                                                 // combinations in max heap.                       
                                                 for                                     (let i = 0; i < N; i++)                       
                                                 for                                     (let j = 0; j < N; j++)                       
                                                 pq.push(A[i] + B[j]);                       
           
                                                 // Pop first N elements                       
                                                 // from max heap and                       
                                                 // display them.                       
                                                 let count = 0;                       
                                                 pq.sort((a, b) => a - b).reverse();                       
                                                 while                                     (count < K)                       
                                                 {                       
                                                 document.write(pq[0] +                                     "<br>"                                     );                       
                                                 pq.shift();                       
                                                 count++;                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                                                 let A = [ 4, 2, 5, 1 ];                       
                                                 let B = [ 8, 0, 5, 3 ];                       
                                                 let N = A.length;                       
                                                 let K = 3;                       
           
                                                 // Function Call                       
                                                 KMaxCombinations(A, B, N, K);                       
           
           
                         // This code is contributed by gfgking                       
                         </script>                       

输出

时间复杂性： O（N） ^2. )

方法2（排序、最大堆、映射）： 我们应该找到一种方法，将搜索空间限制在可能的候选和组合上，而不是强行通过所有可能的和组合。

对数组A和数组B进行排序。
创建一个最大堆，即 C++中的PrimyIyl队列存储和组合以及构成和的数组A和B中元素的索引。堆是按总和排序的。
用最大可能的和组合初始化堆，即（A[N-1]+B[N-1]，其中N是数组的大小）和两个数组中元素的索引（N-1，N-1）。max heap中的元组将是（A[N-1]+B[N-1]，N-1，N-1）。堆按第一个值排序，即两个元素的和。
弹出堆以获得当前最大和，以及构成和的元素的索引。让元组为（sum，i，j）。
1. 下一步将（A[i-1]+B[j]，i-1，j）和（A[i]+B[j-1]，i，j-1）插入最大堆，但确保（i-1，j）和（i，j-1）这对索引不是已存在于最大堆中。要检查这一点，我们可以使用在C++中设置 .
2. 回到4，直到K次。

以下是上述方法的实施情况：

CPP

                         // An efficient C++ program to find top K elements                       
                         // from two arrays.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function prints k maximum possible combinations                       
                         void                                     KMaxCombinations(vector<                                     int                                     >& A,                       
                                                 vector<                                     int                                     >& B,                                     int                                     K)                       
                         {                       
                                                 // sort both arrays A and B                       
                                                 sort(A.begin(), A.end());                       
                                                 sort(B.begin(), B.end());                       
           
                                                 int                                     N = A.size();                       
           
                                                 // Max heap which contains tuple of the format                       
                                                 // (sum, (i, j)) i and j are the indices                       
                                                 // of the elements from array A                       
                                                 // and array B which make up the sum.                       
                                                 priority_queue<pair<                                     int                                     , pair<                                     int                                     ,                                     int                                     > > > pq;                       
           
                                                 // my_set is used to store the indices of                       
                                                 // the  pair(i, j) we use my_set to make sure                       
                                                 // the indices doe not repeat inside max heap.                       
                                                 set<pair<                                     int                                     ,                                     int                                     > > my_set;                       
           
                                                 // initialize the heap with the maximum sum                       
                                                 // combination ie (A[N - 1] + B[N - 1])                       
                                                 // and also push indices (N - 1, N - 1) along                       
                                                 // with sum.                       
                                                 pq.push(make_pair(A[N - 1] + B[N - 1],                       
                                                 make_pair(N - 1, N - 1)));                       
           
                                                 my_set.insert(make_pair(N - 1, N - 1));                       
           
                                                 // iterate upto K                       
                                                 for                                     (                                     int                                     count = 0; count < K; count++)                       
                                                 {                       
                                                 // tuple format (sum, (i, j)).                       
                                                 pair<                                     int                                     , pair<                                     int                                     ,                                     int                                     > > temp = pq.top();                       
                                                 pq.pop();                       
           
                                                 cout << temp.first << endl;                       
           
                                                 int                                     i = temp.second.first;                       
                                                 int                                     j = temp.second.second;                       
           
                                                 int                                     sum = A[i - 1] + B[j];                       
           
                                                 // insert (A[i - 1] + B[j], (i - 1, j))                       
                                                 // into max heap.                       
                                                 pair<                                     int                                     ,                                     int                                     > temp1 = make_pair(i - 1, j);                       
           
                                                 // insert only if the pair (i - 1, j) is                       
                                                 // not already present inside the map i.e.                       
                                                 // no repeating pair should be present inside                       
                                                 // the heap.                       
                                                 if                                     (my_set.find(temp1) == my_set.end())                       
                                                 {                       
                                                 pq.push(make_pair(sum, temp1));                       
                                                 my_set.insert(temp1);                       
                                                 }                       
           
                                                 // insert (A[i] + B[j - 1], (i, j - 1))                       
                                                 // into max heap.                       
                                                 sum = A[i] + B[j - 1];                       
                                                 temp1 = make_pair(i, j - 1);                       
           
                                                 // insert only if the pair (i, j - 1)                       
                                                 // is not present inside the heap.                       
                                                 if                                     (my_set.find(temp1) == my_set.end())                       
                                                 {                       
                                                 pq.push(make_pair(sum, temp1));                       
                                                 my_set.insert(temp1);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver Code.                       
                         int                                     main()                       
                         {                       
                                                 vector<                                     int                                     > A = { 1, 4, 2, 3 };                       
                                                 vector<                                     int                                     > B = { 2, 5, 1, 6 };                       
                                                 int                                     K = 4;                       
                                   
                                                 // Function call                       
                                                 KMaxCombinations(A, B, K);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // An efficient Java program to find                       
                         // top K elements from two arrays.                       
           
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                                 public                                     static                                     void                                     MaxPairSum(Integer[] A,                       
                                                 Integer[] B,                       
                                                 int                                     N,                                     int                                     K)                       
                                                 {                       
                                                 // sort both arrays A and B                       
                                                 Arrays.sort(A);                       
                                                 Arrays.sort(B);                       
                                   
                                                 // Max heap which contains Pair of                       
                                                 // the format (sum, (i, j)) i and j are                       
                                                 // the indices of the elements from                       
                                                 // array A and array B which make up the sum.                       
                                                 PriorityQueue<PairSum> sums                       
                                                 =                                     new                                     PriorityQueue<PairSum>();                       
                                   
                                                 // pairs is used to store the indices of                       
                                                 // the  Pair(i, j) we use pairs to make sure                       
                                                 // the indices doe not repeat inside max heap.                       
                                                 HashSet<Pair> pairs =                                     new                                     HashSet<Pair>();                       
                                   
                                                 // initialize the heap with the maximum sum                       
                                                 // combination ie (A[N - 1] + B[N - 1])                       
                                                 // and also push indices (N - 1, N - 1) along                       
                                                 // with sum.                       
                                                 int                                     l = N -                                     1                                     ;                       
                                                 int                                     m = N -                                     1                                     ;                       
                                                 pairs.add(                                     new                                     Pair(l, m));                       
                                                 sums.add(                                     new                                     PairSum(A[l] + B[m], l, m));                       
                                   
                                                 // iterate upto K                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < K; i++)                       
                                                 {                       
                                                 // Poll the element from the                       
                                                 // maxheap in theformat (sum, (l,m))                       
                                                 PairSum max = sums.poll();                       
                                                 System.out.println(max.sum);                       
                                                 l = max.l -                                     1                                     ;                       
                                                 m = max.m;                       
                                                 // insert only if l and m are greater                       
                                                 // than 0 and the pair (l, m) is                       
                                                 // not already present inside set i.e.                       
                                                 // no repeating pair should be                       
                                                 // present inside the heap.                       
                                                 if                                     (l >=                                     0                                     && m >=                                     0                       
                                                 && !pairs.contains(                                     new                                     Pair(l, m)))                       
                                                 {                       
                                                 // insert (A[l]+B[m], (l, m))                       
                                                 // in the heap                       
                                                 sums.add(                                     new                                     PairSum(A[l]                       
                                                 + B[m], l, m));                       
                                                 pairs.add(                                     new                                     Pair(l, m));                       
                                                 }                       
           
                                                 l = max.l;                       
                                                 m = max.m -                                     1                                     ;                       
           
                                                 // insert only if l and m are                       
                                                 // greater than 0 and                       
                                                 // the pair (l, m) is not                       
                                                 // already present inside                       
                                                 // set i.e. no repeating pair                       
                                                 // should be present                       
                                                 // inside the heap.                       
                                                 if                                     (l >=                                     0                                     && m >=                                     0                       
                                                 && !pairs.contains(                                     new                                     Pair(l, m)))                       
                                                 {                       
                                                 // insert (A[i1]+B[i2], (i1, i2))                       
                                                 // in the heap                       
                                                 sums.add(                                     new                                     PairSum(A[l]                       
                                                 + B[m], l, m));                       
                                                 pairs.add(                                     new                                     Pair(l, m));                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 Integer A[] = {                                     1                                     ,                                     4                                     ,                                     2                                     ,                                     3                                     };                       
                                                 Integer B[] = {                                     2                                     ,                                     5                                     ,                                     1                                     ,                                     6                                     };                       
                                                 int                                     N = A.length;                       
                                                 int                                     K =                                     4                                     ;                       
           
                                                 // Function Call                       
                                                 MaxPairSum(A, B, N, K);                       
                                                 }                       
           
                                                 public                                     static                                     class                                     Pair {                       
           
                                                 public                                     Pair(                                     int                                     l,                                     int                                     m)                       
                                                 {                       
                                                 this                                     .l = l;                       
                                                 this                                     .m = m;                       
                                                 }                       
           
                                                 int                                     l;                       
                                                 int                                     m;                       
           
                                                 @Override                                     public                                     boolean                                     equals(Object o)                       
                                                 {                       
                                                 if                                     (o ==                                     null                                     ) {                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 if                                     (!(o                                     instanceof                                     Pair)) {                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 Pair obj = (Pair)o;                       
                                                 return                                     (l == obj.l && m == obj.m);                       
                                                 }                       
           
                                                 @Override                                     public                                     int                                     hashCode()                       
                                                 {                       
                                                 return                                     Objects.hash(l, m);                       
                                                 }                       
                                                 }                       
           
                                                 public                                     static                                     class                                     PairSum                       
                                                 implements                                     Comparable<PairSum> {                       
           
                                                 public                                     PairSum(                                     int                                     sum,                                     int                                     l,                                     int                                     m)                       
                                                 {                       
                                                 this                                     .sum = sum;                       
                                                 this                                     .l = l;                       
                                                 this                                     .m = m;                       
                                                 }                       
           
                                                 int                                     sum;                       
                                                 int                                     l;                       
                                                 int                                     m;                       
           
                                                 @Override                                     public                                     int                                     compareTo(PairSum o)                       
                                                 {                       
                                                 return                                     Integer.compare(o.sum, sum);                       
                                                 }                       
                                                 }                       
                         }                       

输出

时间复杂性： O（N对数N）假设K<=N

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章