Dados dos arreglos arr1[] y arr2[] ordenados en orden ascendente y un número entero K. La tarea es encontrar 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[] . Los tamaños de las arrays pueden ser diferentes. Suponga que todos los elementos son distintos en cada array.
Ejemplos:
Input: a1[] = {1, 7, 11}
a2[] = {2, 4, 6}
k = 3
Output: [1, 2], [1, 4], [1, 6]
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].
Input: a1[] = { 2, 3, 4 }
a2[] = { 1, 6, 5, 8 }
k = 4
Output: [1, 2] [1, 3] [1, 4] [2, 6]
Aquí se ha discutido un enfoque con complejidad temporal O(k*n1) .
Enfoque eficiente: dado que la array ya está ordenada. El siguiente algoritmo se puede seguir para resolver este problema:
- La idea es mantener dos punteros, un puntero apuntando a un par en (a1, a2) y el otro en (a2, a1). Cada vez, compare las sumas de los elementos señalados por los dos pares e imprima el mínimo. Después de esto, incremente el puntero al elemento del par impreso que era más grande que el otro. Esto ayuda a obtener el siguiente k par más pequeño posible.
- Una vez que el puntero se haya actualizado al elemento de modo que comience a apuntar al primer elemento de la array nuevamente, actualice el otro puntero al siguiente valor. Esta actualización se realiza de forma cíclica.
- Además, cuando ambos pares apunten al mismo elemento, actualice los punteros en ambos pares para evitar la impresión de pares adicionales. Actualice el puntero de un par de acuerdo con la regla 1 y el opuesto del otro a la regla 1. Esto se hace para garantizar que se consideren todas las permutaciones y que no haya repeticiones de pares.
A continuación se muestra el funcionamiento del algoritmo para el ejemplo 1:
a1[] = {1, 7, 11}, a2[] = {2, 4}, k = 3
Sean los pares de punteros _uno, _dos
_uno.primero apunta a 1, _uno.segundo apunta a 2 ;
_dos.primero apunta a 2, _dos.segundo apunta a 1
1er par:
Dado que _uno y _dos apuntan a los mismos elementos, imprima el par una vez y actualice
- imprimir [1, 2]
luego actualice _one.first a 1, _one.second a 4 (siguiendo la regla 1);
_dos.primero apunta a 2, _dos.segundo apunta a 7 (opuesto a la regla 1).
Si se siguió la regla 1 para ambos, ambos habrían estado apuntando al 1 y al 4,
y no es posible obtener todas las permutaciones posibles.
2do par:
Dado que a1[_uno.primero] + a2[_uno.segundo] < a1[_dos.segundo] + a2[_dos.primero], imprímalos y actualícelos
- imprimir [1, 4]
luego actualice _uno.primero a 1, _uno.segundo a 2
Dado que _uno.segundo llegó al primer elemento de la array una vez más,
por lo tanto, _uno.primero apunta a 7
Repita el proceso anterior para los K pares restantes
A continuación se muestra la implementación en C++ del enfoque anterior:
C++
// C++ program to print the k smallest
// pairs | Set 2
#include <bits/stdc++.h>
using namespace std;
typedef struct _pair {
int first, second;
} _pair;
// Function to print the K smallest pairs
void printKPairs(int a1[], int a2[],
int size1, int size2, int k)
{
// if k is greater than total pairs
if (k > (size2 * size1)) {
cout << "k pairs don't exist\n";
return;
}
// _pair _one keeps track of
// 'first' in a1 and 'second' in a2
// in _two, _two.first keeps track of
// element in the a2[] and _two.second in a1[]
_pair _one, _two;
_one.first = _one.second = _two.first = _two.second = 0;
int cnt = 0;
// Repeat the above process till
// all K pairs are printed
while (cnt < k) {
// when both the pointers are pointing
// to the same elements (point 3)
if (_one.first == _two.second
&& _two.first == _one.second) {
if (a1[_one.first] < a2[_one.second]) {
cout << "[" << a1[_one.first]
<< ", " << a2[_one.second] << "] ";
// updates according to step 1
_one.second = (_one.second + 1) % size2;
if (_one.second == 0) // see point 2
_one.first = (_one.first + 1) % size1;
// updates opposite to step 1
_two.second = (_two.second + 1) % size2;
if (_two.second == 0)
_two.first = (_two.first + 1) % size2;
}
else {
cout << "[" << a2[_one.second]
<< ", " << a1[_one.first] << "] ";
// updates according to rule 1
_one.first = (_one.first + 1) % size1;
if (_one.first == 0) // see point 2
_one.second = (_one.second + 1) % size2;
// updates opposite to rule 1
_two.first = (_two.first + 1) % size2;
if (_two.first == 0) // see point 2
_two.second = (_two.second + 1) % size1;
}
}
// else update as necessary (point 1)
else if (a1[_one.first] + a2[_one.second]
<= a2[_two.first] + a1[_two.second]) {
if (a1[_one.first] < a2[_one.second]) {
cout << "[" << a1[_one.first] << ", "
<< a2[_one.second] << "] ";
// updating according to rule 1
_one.second = ((_one.second + 1) % size2);
if (_one.second == 0) // see point 2
_one.first = (_one.first + 1) % size1;
}
else {
cout << "[" << a2[_one.second] << ", "
<< a1[_one.first] << "] ";
// updating according to rule 1
_one.first = ((_one.first + 1) % size1);
if (_one.first == 0) // see point 2
_one.second = (_one.second + 1) % size2;
}
}
else if (a1[_one.first] + a2[_one.second]
> a2[_two.first] + a1[_two.second]) {
if (a2[_two.first] < a1[_two.second]) {
cout << "[" << a2[_two.first] << ", " << a1[_two.second] << "] ";
// updating according to rule 1
_two.first = ((_two.first + 1) % size2);
if (_two.first == 0) // see point 2
_two.second = (_two.second + 1) % size1;
}
else {
cout << "[" << a1[_two.second]
<< ", " << a2[_two.first] << "] ";
// updating according to rule 1
_two.second = ((_two.second + 1) % size1);
if (_two.second == 0) // see point 2
_two.first = (_two.first + 1) % size1;
}
}
cnt++;
}
}
// Driver Code
int main()
{
int a1[] = { 2, 3, 4 };
int a2[] = { 1, 6, 5, 8 };
int size1 = sizeof(a1) / sizeof(a1[0]);
int size2 = sizeof(a2) / sizeof(a2[0]);
int k = 4;
printKPairs(a1, a2, size1, size2, k);
return 0;
}
Java
// Java program to print
// the k smallest pairs
// | Set 2
import java.util.*;
class GFG{
static class _pair
{
int first, second;
};
// Function to print the K
// smallest pairs
static void printKPairs(int a1[], int a2[],
int size1, int size2,
int k)
{
// if k is greater than
// total pairs
if (k > (size2 * size1))
{
System.out.print("k pairs don't exist\n");
return;
}
// _pair _one keeps track of
// 'first' in a1 and 'second' in a2
// in _two, _two.first keeps track of
// element in the a2[] and _two.second
// in a1[]
_pair _one = new _pair();
_pair _two = new _pair();
_one.first = _one.second =
_two.first = _two.second = 0;
int cnt = 0;
// Repeat the above process
// till all K pairs are printed
while (cnt < k)
{
// when both the pointers are
// pointing to the same elements
// (point 3)
if (_one.first == _two.second &&
_two.first == _one.second)
{
if (a1[_one.first] <
a2[_one.second])
{
System.out.print("[" + a1[_one.first] +
", " + a2[_one.second] +
"] ");
// updates according to step 1
_one.second = (_one.second + 1) %
size2;
// see point 2
if (_one.second == 0)
_one.first = (_one.first + 1) %
size1;
// updates opposite to step 1
_two.second = (_two.second + 1) %
size2;
if (_two.second == 0)
_two.first = (_two.first + 1) %
size2;
}
else
{
System.out.print("[" + a2[_one.second] +
", " + a1[_one.first] +
"] ");
// updates according to rule 1
_one.first = (_one.first + 1) %
size1;
// see point 2
if (_one.first == 0)
_one.second = (_one.second + 1) %
size2;
// updates opposite to rule 1
_two.first = (_two.first + 1) %
size2;
// see point 2
if (_two.first == 0)
_two.second = (_two.second + 1) %
size1;
}
}
// else update as
// necessary (point 1)
else if (a1[_one.first] +
a2[_one.second] <=
a2[_two.first] +
a1[_two.second])
{
if (a1[_one.first] <
a2[_one.second])
{
System.out.print("[" + a1[_one.first] +
", " + a2[_one.second] +
"] ");
// updating according to rule 1
_one.second = ((_one.second + 1) %
size2);
// see point 2
if (_one.second == 0)
_one.first = (_one.first + 1) %
size1;
}
else
{
System.out.print("[" + a2[_one.second] +
", " + a1[_one.first] +
"] ");
// updating according to rule 1
_one.first = ((_one.first + 1) %
size1);
// see point 2
if (_one.first == 0)
_one.second = (_one.second + 1) %
size2;
}
}
else if (a1[_one.first] +
a2[_one.second] >
a2[_two.first] +
a1[_two.second])
{
if (a2[_two.first] <
a1[_two.second])
{
System.out.print("[" + a2[_two.first] +
", " + a1[_two.second] +
"] ");
// updating according to rule 1
_two.first = ((_two.first + 1) %
size2);
// see point 2
if (_two.first == 0)
_two.second = (_two.second + 1) %
size1;
}
else {
System.out.print("[" + a1[_two.second] +
", " + a2[_two.first] +
"] ");
// updating according to rule 1
_two.second = ((_two.second + 1) %
size1);
// see point 2
if (_two.second == 0)
_two.first = (_two.first + 1) %
size1;
}
}
cnt++;
}
}
// Driver Code
public static void main(String[] args)
{
int a1[] = {2, 3, 4};
int a2[] = {1, 6, 5, 8};
int size1 = a1.length;
int size2 = a2.length;
int k = 4;
printKPairs(a1, a2,
size1, size2, k);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to print the k smallest
# pairs | Set 2
# Function to print the K smallest pairs
def printKPairs(a1, a,size1, size2, k):
# if k is greater than total pairs
if (k > (size2 * size1)):
print("k pairs don't exist\n")
return
# _pair _one keeps track of
# 'first' in a1 and 'second' in a2
# in _two, _two[0] keeps track of
# element in the a2and _two[1] in a1[]
_one, _two = [0, 0], [0, 0]
cnt = 0
# Repeat the above process till
# all K pairs are printed
while (cnt < k):
# when both the pointers are pointing
# to the same elements (po3)
if (_one[0] == _two[1]
and _two[0] == _one[1]):
if (a1[_one[0]] < a2[_one[1]]):
print("[", a1[_one[0]], ", ",
a2[_one[1]],"] ", end=" ")
# updates according to step 1
_one[1] = (_one[1] + 1) % size2
if (_one[1] == 0): #see po2
_one[0] = (_one[0] + 1) % size1
# updates opposite to step 1
_two[1] = (_two[1] + 1) % size2
if (_two[1] == 0):
_two[0] = (_two[0] + 1) % size2
else:
print("[",a2[_one[1]]
,", ",a1[_one[0]],"] ",end=" ")
# updates according to rule 1
_one[0] = (_one[0] + 1) % size1
if (_one[0] == 0): #see po2
_one[1] = (_one[1] + 1) % size2
# updates opposite to rule 1
_two[0] = (_two[0] + 1) % size2
if (_two[0] == 0): #see po2
_two[1] = (_two[1] + 1) % size1
# else update as necessary (po1)
elif (a1[_one[0]] + a2[_one[1]]
<= a2[_two[0]] + a1[_two[1]]):
if (a1[_one[0]] < a2[_one[1]]):
print("[",a1[_one[0]],", ",
a2[_one[1]],"] ",end=" ")
# updating according to rule 1
_one[1] = ((_one[1] + 1) % size2)
if (_one[1] == 0): # see po2
_one[0] = (_one[0] + 1) % size1
else:
print("[",a2[_one[1]],", ",
a1[_one[0]],"] ", end=" ")
# updating according to rule 1
_one[0] = ((_one[0] + 1) % size1)
if (_one[0] == 0): # see po2
_one[1] = (_one[1] + 1) % size2
elif (a1[_one[0]] + a2[_one[1]]
> a2[_two[0]] + a1[_two[1]]):
if (a2[_two[0]] < a1[_two[1]]):
print("[",a2[_two[0]],", ",a1[_two[1]],"] ",end=" ")
# updating according to rule 1
_two[0] = ((_two[0] + 1) % size2)
if (_two[0] == 0): #see po2
_two[1] = (_two[1] + 1) % size1
else:
print("[",a1[_two[1]]
,", ",a2[_two[0]],"] ",end=" ")
# updating according to rule 1
_two[1] = ((_two[1] + 1) % size1)
if (_two[1] == 0): #see po2
_two[0] = (_two[0] + 1) % size1
cnt += 1
# Driver Code
if __name__ == '__main__':
a1= [2, 3, 4]
a2= [1, 6, 5, 8]
size1 = len(a1)
size2 = len(a2)
k = 4
printKPairs(a1, a2, size1, size2, k)
# This code is contributed by mohit kumar 29
C#
// C# program to print
// the k smallest pairs
// | Set 2
using System;
class GFG{
public class _pair
{
public int first,
second;
};
// Function to print the K
// smallest pairs
static void printKPairs(int []a1, int []a2,
int size1, int size2,
int k)
{
// if k is greater than
// total pairs
if (k > (size2 * size1))
{
Console.Write("k pairs don't exist\n");
return;
}
// _pair _one keeps track of
// 'first' in a1 and 'second' in a2
// in _two, _two.first keeps track of
// element in the a2[] and _two.second
// in a1[]
_pair _one = new _pair();
_pair _two = new _pair();
_one.first = _one.second =
_two.first = _two.second = 0;
int cnt = 0;
// Repeat the above process
// till all K pairs are printed
while (cnt < k)
{
// when both the pointers are
// pointing to the same elements
// (point 3)
if (_one.first == _two.second &&
_two.first == _one.second)
{
if (a1[_one.first] <
a2[_one.second])
{
Console.Write("[" + a1[_one.first] +
", " + a2[_one.second] +
"] ");
// updates according to step 1
_one.second = (_one.second + 1) %
size2;
// see point 2
if (_one.second == 0)
_one.first = (_one.first + 1) %
size1;
// updates opposite to step 1
_two.second = (_two.second + 1) %
size2;
if (_two.second == 0)
_two.first = (_two.first + 1) %
size2;
}
else
{
Console.Write("[" + a2[_one.second] +
", " + a1[_one.first] +
"] ");
// updates according to rule 1
_one.first = (_one.first + 1) %
size1;
// see point 2
if (_one.first == 0)
_one.second = (_one.second + 1) %
size2;
// updates opposite to rule 1
_two.first = (_two.first + 1) %
size2;
// see point 2
if (_two.first == 0)
_two.second = (_two.second + 1) %
size1;
}
}
// else update as
// necessary (point 1)
else if (a1[_one.first] +
a2[_one.second] <=
a2[_two.first] +
a1[_two.second])
{
if (a1[_one.first] <
a2[_one.second])
{
Console.Write("[" + a1[_one.first] +
", " + a2[_one.second] +
"] ");
// updating according to rule 1
_one.second = ((_one.second + 1) %
size2);
// see point 2
if (_one.second == 0)
_one.first = (_one.first + 1) %
size1;
}
else
{
Console.Write("[" + a2[_one.second] +
", " + a1[_one.first] +
"] ");
// updating according to rule 1
_one.first = ((_one.first + 1) %
size1);
// see point 2
if (_one.first == 0)
_one.second = (_one.second + 1) %
size2;
}
}
else if (a1[_one.first] +
a2[_one.second] >
a2[_two.first] +
a1[_two.second])
{
if (a2[_two.first] <
a1[_two.second])
{
Console.Write("[" + a2[_two.first] +
", " + a1[_two.second] +
"] ");
// updating according to rule 1
_two.first = ((_two.first + 1) %
size2);
// see point 2
if (_two.first == 0)
_two.second = (_two.second + 1) %
size1;
}
else {
Console.Write("[" + a1[_two.second] +
", " + a2[_two.first] +
"] ");
// updating according to rule 1
_two.second = ((_two.second + 1) %
size1);
// see point 2
if (_two.second == 0)
_two.first = (_two.first + 1) %
size1;
}
}
cnt++;
}
}
// Driver Code
public static void Main(String[] args)
{
int []a1 = {2, 3, 4};
int []a2 = {1, 6, 5, 8};
int size1 = a1.Length;
int size2 = a2.Length;
int k = 4;
printKPairs(a1, a2,
size1,
size2, k);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to print
// the k smallest pairs
// | Set 2
// Function to print the K
// smallest pairs
function printKPairs(a1,a2,size1,size2,k)
{
// if k is greater than
// total pairs
if (k > (size2 * size1))
{
document.write("k pairs don't exist\n");
return;
}
// _pair _one keeps track of
// 'first' in a1 and 'second' in a2
// in _two, _two[0] keeps track of
// element in the a2[] and _two[1]
// in a1[]
let _one = [0,0];
let _two = [0,0];
let cnt = 0;
// Repeat the above process
// till all K pairs are printed
while (cnt < k)
{
// when both the pointers are
// pointing to the same elements
// (point 3)
if (_one[0] == _two[1] &&
_two[0] == _one[1])
{
if (a1[_one[0]] <
a2[_one[1]])
{
document.write("[" + a1[_one[0]] +
", " + a2[_one[1]] +
"] ");
// updates according to step 1
_one[1] = (_one[1] + 1) %
size2;
// see point 2
if (_one[1] == 0)
_one[0] = (_one[0] + 1) %
size1;
// updates opposite to step 1
_two[1] = (_two[1] + 1) %
size2;
if (_two[1] == 0)
_two[0] = (_two[0] + 1) %
size2;
}
else
{
document.write("[" + a2[_one[1]] +
", " + a1[_one[0]] +
"] ");
// updates according to rule 1
_one[0] = (_one[0] + 1) %
size1;
// see point 2
if (_one[0] == 0)
_one[1] = (_one[1] + 1) %
size2;
// updates opposite to rule 1
_two[0] = (_two[0] + 1) %
size2;
// see point 2
if (_two[0] == 0)
_two[1] = (_two[1] + 1) %
size1;
}
}
// else update as
// necessary (point 1)
else if (a1[_one[0]] +
a2[_one[1]] <=
a2[_two[0]] +
a1[_two[1]])
{
if (a1[_one[0]] <
a2[_one[1]])
{
document.write("[" + a1[_one[0]] +
", " + a2[_one[1]] +
"] ");
// updating according to rule 1
_one[1] = ((_one[1] + 1) %
size2);
// see point 2
if (_one[1] == 0)
_one[0] = (_one[0] + 1) %
size1;
}
else
{
document.write("[" + a2[_one[1]] +
", " + a1[_one[0]] +
"] ");
// updating according to rule 1
_one[0] = ((_one[0] + 1) %
size1);
// see point 2
if (_one[0] == 0)
_one[1] = (_one[1] + 1) %
size2;
}
}
else if (a1[_one[0]] +
a2[_one[1]] >
a2[_two[0]] +
a1[_two[1]])
{
if (a2[_two[0]] <
a1[_two[1]])
{
document.write("[" + a2[_two[0]] +
", " + a1[_two[1]] +
"] ");
// updating according to rule 1
_two[0] = ((_two[0] + 1) %
size2);
// see point 2
if (_two[0] == 0)
_two[1] = (_two[1] + 1) %
size1;
}
else {
document.write("[" + a1[_two[1]] +
", " + a2[_two[0]] +
"] ");
// updating according to rule 1
_two[1] = ((_two[1] + 1) %
size1);
// see point 2
if (_two[1] == 0)
_two[0] = (_two[0] + 1) %
size1;
}
}
cnt++;
}
}
// Driver Code
let a1=[2, 3, 4];
let a2=[1, 6, 5, 8];
let size1 = a1.length;
let size2 = a2.length;
let k = 4;
printKPairs(a1, a2,
size1, size2, k);
// This code is contributed by unknown2108
</script>
Producción:
[1, 2] [1, 3] [1, 4] [2, 6]
Complejidad del tiempo : O(K)
Publicación traducida automáticamente
Artículo escrito por nth_underdog y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA