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))
Espacio auxiliar: O (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.
Implementación:
C++
// 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;
}
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*/
Python3
# 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
C#
// C# code to print first k pairs with
// least with least sum from two arrays.
using System;
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)
{
Console.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.
int []index2 = new int[n1];
while (k > 0)
{
// Initialize current pair sum as infinite
int min_sum = int.MaxValue;
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]];
}
}
Console.Write("(" + 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 Parashar.
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>
Producción
(1, 2) (1, 4) (3, 2) (3, 4)
Complejidad de Tiempo : O(k*n1)
Espacio Auxiliar : O(n1)
Método 3: uso de clasificación, montón mínimo, mapa
En lugar de aplicar fuerza bruta a través de todas las posibles combinaciones de sumas, deberíamos encontrar una forma de limitar nuestro espacio de búsqueda a posibles combinaciones de sumas candidatas.
- 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.
- 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.
- 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.
Implementación:
C++
// 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)
{
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 does 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 = 8;
kSmallestPair(A, B, K);
return 0;
}
// This code is contributed by Dhairya.
Producción
(1, 2) (1, 4) (1, 5)
Complejidad de tiempo: O(n*logn) asumiendo k<=n
Espacio auxiliar: O(n) ya que estamos usando espacio extra
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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