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.
Javascript
<script>
// javascript program to prints first k pairs with least sum from two
// arrays.
// Function to find k pairs with least sum such
// that one element of a pair is from arr1[] and
// other element is from arr2[]
function kSmallestPair(arr1,n1,arr2,n2,k)
{
if (k > n1*n2)
{
document.write("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.
let index2 = new Array(n1);
index2.fill(0);
while (k > 0)
{
// Initialize current pair sum as infinite
let min_sum = Number.MAX_VALUE;
let 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 (let 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]];
}
}
document.write("(" + arr1[min_index] + ", "
+ arr2[index2[min_index]] + ") ");
index2[min_index]++;
k--;
}
}
let arr1 = [1, 3, 11];
let n1 = arr1.length;
let arr2 = [2, 4, 8];
let n2 = arr2.length;
let k = 4;
kSmallestPair( arr1, n1, arr2, n2, k);
</script>
(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