Programa Python3 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.  

# Python3 program to prints first k pairs with least sum from two
# arrays.
 
import sys
# Function to find k pairs with least sum such
# that one element of a pair is from arr1[] and
# other element is from arr2[]
def kSmallestPair(arr1, n1, arr2, n2, k):
    if (k > n1*n2):
        print("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.
    index2 = [0 for i in range(n1)]
 
    while (k > 0):
        # Initialize current pair sum as infinite
        min_sum = sys.maxsize
        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 i1 in range(0,n1,1):
            # Check if current element of arr1[] plus
            # element of array2 to be used gives minimum
            # sum
            if (index2[i1] < n2 and 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]]
         
        print("(",arr1[min_index],",",arr2[index2[min_index]],")",end = " ")
 
        index2[min_index] += 1
 
        k -= 1
 
# Driver code
if __name__ == '__main__':
    arr1 = [1, 3, 11]
    n1 = len(arr1)
 
    arr2 = [2, 4, 8]
    n2 = len(arr2)
 
    k = 4
    kSmallestPair( arr1, n1, arr2, n2, k)
 
# This code is contributed by
# Shashank_Sharma

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

Complejidad de tiempo: O(k*n1), donde n1 es el tamaño de la array dada y k es el número entero dado.

Espacio auxiliar: O(n1), donde n1 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!