Programa C++ para encontrar k pares con sumas más pequeñas en dos arrays

Dadas dos arrays de enteros arr1[] y arr2[] ordenadas en orden ascendente y un entero k. Encuentre k pares con las sumas más pequeñas tales que un elemento de un par pertenezca a arr1[] y otro elemento pertenezca a arr2[]
Ejemplos: 

Input :  arr1[] = {1, 7, 11}
         arr2[] = {2, 4, 6}
         k = 3
Output : [1, 2],
         [1, 4],
         [1, 6]
Explanation: The first 3 pairs are returned 
from the sequence [1, 2], [1, 4], [1, 6], 
[7, 2], [7, 4], [11, 2], [7, 6], [11, 4], 
[11, 6]

Método 1 (Simple)  

1. Encuentra todos los pares y almacena sus sumas. La complejidad temporal de este paso es O(n1 * n2) donde n1 y n2 son tamaños de arrays de entrada.
2. Luego ordena los pares según la suma. La complejidad temporal de este paso es O(n1 * n2 * log (n1 * n2))

Complejidad de tiempo general: O (n1 * n2 * log (n1 * n2))
Método 2 (eficiente): 
uno por uno encontramos k pares de sumas más pequeñas, comenzando por el par de sumas más pequeñas. La idea es realizar un seguimiento de todos los elementos de arr2[] que ya se han considerado para cada elemento arr1[i1] de modo que en una iteración solo consideremos el siguiente elemento. Para este propósito, usamos una array de índices index2[] para rastrear los índices de los siguientes elementos en la otra array. Simplemente significa qué elemento de la segunda array se agregará con el elemento de la primera array en todas y cada una de las iteraciones. Incrementamos el valor en la array de índices para el elemento que forma el siguiente par de valores mínimos.  

// C++ program to prints first k pairs with least sum from two
// arrays.
#include<bits/stdc++.h>
 
using namespace std;
 
// Function to find k pairs with least sum such
// that one element of a pair is from arr1[] and
// other element is from arr2[]
void kSmallestPair(int arr1[], int n1, int arr2[],
                                   int n2, int k)
{
    if (k > n1*n2)
    {
        cout << "k pairs don't exist";
        return ;
    }
 
    // Stores current index in arr2[] for
    // every element of arr1[]. Initially
    // all values are considered 0.
    // Here current index is the index before
    // which all elements are considered as
    // part of output.
    int index2[n1];
    memset(index2, 0, sizeof(index2));
 
    while (k > 0)
    {
        // Initialize current pair sum as infinite
        int min_sum = INT_MAX;
        int min_index = 0;
 
        // To pick next pair, traverse for all elements
        // of arr1[], for every element, find corresponding
        // current element in arr2[] and pick minimum of
        // all formed pairs.
        for (int i1 = 0; i1 < n1; i1++)
        {
            // Check if current element of arr1[] plus
            // element of array2 to be used gives minimum
            // sum
            if (index2[i1] < n2 &&
                arr1[i1] + arr2[index2[i1]] < min_sum)
            {
                // Update index that gives minimum
                min_index = i1;
 
                // update minimum sum
                min_sum = arr1[i1] + arr2[index2[i1]];
            }
        }
 
        cout << "(" << arr1[min_index] << ", "
             << arr2[index2[min_index]] << ") ";
 
        index2[min_index]++;
 
        k--;
    }
}
 
// Driver code
int main()
{
    int arr1[] = {1, 3, 11};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
 
    int arr2[] = {2, 4, 8};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
 
    int k = 4;
    kSmallestPair( arr1, n1, arr2, n2, k);
 
    return 0;
}

(1, 2) (1, 4) (3, 2) (3, 4) 

Complejidad de tiempo: O(k*n1), donde n1 representa el tamaño de la array dada.
Espacio auxiliar: O(n1), donde n1 representa el tamaño de la array dada.

Método 3: uso de clasificación, montón mínimo, mapa 
En lugar de utilizar la fuerza bruta en todas las combinaciones de sumas posibles, debemos encontrar una forma de limitar nuestro espacio de búsqueda a posibles combinaciones de sumas candidatas.  

1. Ordene ambas arrays, la array A y la array B.
2. Cree un montón mínimo, es decir, cola de prioridad en C++ para almacenar las combinaciones de suma junto con los índices de los elementos de las arrays A y B que componen la suma. El montón está ordenado por la suma.
3. Inicialice el montón con la combinación de suma mínima posible, es decir (A[0] + B[0]) y con los índices de los elementos de ambas arrays (0, 0). La tupla dentro del montón mínimo será (A[0] + B[0], 0, 0). El montón está ordenado por el primer valor, es decir, la suma de ambos elementos.
4. Haga estallar el montón para obtener la suma más pequeña actual y junto con los índices del elemento que componen la suma. Sea la tupla (suma, i, j). 
   • A continuación, inserte (A[i + 1] + B[j], i + 1, j) y (A[i] + B[j + 1], i, j + 1) en el montón mínimo, pero asegúrese de que un par de índices, es decir, (i + 1, j) y (i, j + 1) aún no están presentes en el montón mínimo. Para verificar esto, podemos usar set en C++.
   • Vuelva a 4 hasta K veces.

// C++ program to Prints
// first k pairs with
// least sum from two arrays.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find k pairs
// with least sum such
// that one element of a pair
// is from arr1[] and
// other element is from arr2[]
void kSmallestPair(vector<int> A, vector<int> B, int K)
{
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
 
    int n = A.size();
 
    // Min 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> >,
                   vector<pair<int, pair<int, int> > >,
                   greater<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 min heap.
 
    set<pair<int, int> > my_set;
 
    // initialize the heap with the minimum sum
    // combination i.e. (A[0] + B[0])
    // and also push indices (0,0) along
    // with sum.
 
    pq.push(make_pair(A[0] + B[0], make_pair(0, 0)));
 
    my_set.insert(make_pair(0, 0));
 
    // iterate upto K
    int flag=1;
    for (int count = 0; count < K && flag; count++) {
 
        // tuple format (sum, i, j).
        pair<int, pair<int, int> > temp = pq.top();
        pq.pop();
 
        int i = temp.second.first;
        int j = temp.second.second;
 
        cout << "(" << A[i] << ", " << B[j] << ")"
             << endl; // Extracting pair with least sum such
                      // that one element is from arr1 and
                      // another is from arr2
 
        // check if i+1 is in the range of our first array A
        flag=0;
        if (i + 1 < A.size()) {
            int sum = A[i + 1] + B[j];
            // insert (A[i + 1] + B[j], (i + 1, j))
            // into min 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);
            }
          flag=1;
        }
        // check if j+1 is in the range of our second array
        // B
        if (j + 1 < B.size()) {
            // insert (A[i] + B[j + 1], (i, j + 1))
            // into min heap.
 
            int sum = A[i] + B[j + 1];
            pair<int, int> 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);
            }
          flag=1;
        }
    }
}
 
// Driver Code.
int main()
{
    vector<int> A = { 1 };
    vector<int> B = { 2, 4, 5, 9 };
    int K = 3;
    kSmallestPair(A, B, K);
    return 0;
}
 
// This code is contributed by Dhairya.

(1, 2)
(1, 4)
(1, 5)

Complejidad de tiempo: O(n*logn) asumiendo k<=n.

Espacio auxiliar: O(n), donde n es el tamaño de la array dada.

¡ Consulte el artículo completo sobre Encontrar k pares con las sumas más pequeñas en dos arrays para obtener más detalles!