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)
- 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.
- 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.
Java
// Java code to print first k pairs with least
// sum from two arrays.
import java.io.*;
class KSmallestPair
{
// Function to find k pairs with least sum such
// that one element of a pair is from arr1[] and
// other element is from arr2[]
static void kSmallestPair(int arr1[], int n1, int arr2[],
int n2, int k)
{
if (k > n1*n2)
{
System.out.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.
int index2[] = new int[n1];
while (k > 0)
{
// Initialize current pair sum as infinite
int min_sum = Integer.MAX_VALUE;
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]];
}
}
System.out.print("(" + arr1[min_index] + ", " +
arr2[index2[min_index]]+ ") ");
index2[min_index]++;
k--;
}
}
// Driver code
public static void main (String[] args)
{
int arr1[] = {1, 3, 11};
int n1 = arr1.length;
int arr2[] = {2, 4, 8};
int n2 = arr2.length;
int k = 4;
kSmallestPair( arr1, n1, arr2, n2, k);
}
}
/*This code is contributed by Prakriti Gupta*/
(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!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA