Dados dos arreglos ordenados y un número x, encuentra el par cuya suma es más cercana a x y el par tiene un elemento de cada arreglo .
Nos dan dos arreglos ar1[0…m-1] y ar2[0..n-1] y un número x, necesitamos encontrar el par ar1[i] + ar2[j] tal que el valor absoluto de (ar1 [i] + ar2[j] – x) es mínimo.
Ejemplo:
Input: ar1[] = {1, 4, 5, 7};
ar2[] = {10, 20, 30, 40};
x = 32
Output: 1 and 30
Input: ar1[] = {1, 4, 5, 7};
ar2[] = {10, 20, 30, 40};
x = 50
Output: 7 and 40
Recomendamos encarecidamente minimizar su navegador y probarlo usted mismo primero.
Una solución simple es ejecutar dos bucles. El ciclo externo considera cada elemento de la primera array y el ciclo interno verifica el par en la segunda array. Realizamos un seguimiento de la diferencia mínima entre ar1[i] + ar2[j] y x.
Podemos hacerlo en tiempo O(n) usando los siguientes pasos.
1) Combinar dos arrays dadas en una array auxiliar de tamaño m+n utilizando el proceso de combinación de clasificación por combinación . Mientras se fusiona, mantenga otra array booleana de tamaño m+n para indicar si el elemento actual en la array fusionada es de ar1[] o ar2[].
2) Considere la array fusionada y use el algoritmo de tiempo lineal para encontrar el par con la suma más cercana a x. Una cosa adicional que necesitamos considerar solo aquellos pares que tienen un elemento de ar1[] y otro de ar2[], usamos la array booleana para este propósito.
¿Podemos hacerlo en una sola pasada y O(1) espacio extra?
La idea es comenzar desde el lado izquierdo de una array y el lado derecho de otra array, y usar el mismo algoritmo que el paso 2 del enfoque anterior. A continuación se detalla el algoritmo.
1) Initialize a variable diff as infinite (Diff is used to store the
difference between pair and x). We need to find the minimum diff.
2) Initialize two index variables l and r in the given sorted array.
(a) Initialize first to the leftmost index in ar1: l = 0
(b) Initialize second the rightmost index in ar2: r = n-1
3) Loop while l< length.ar1 and r>=0
(a) If abs(ar1[l] + ar2[r] - sum) < diff then
update diff and result
(b) If (ar1[l] + ar2[r] < sum ) then l++
(c) Else r--
4) Print the result.
A continuación se muestra la implementación de este enfoque.
C++
// C++ program to find the pair from two sorted arrays such
// that the sum of pair is closest to a given number x
#include <iostream>
#include <climits>
#include <cstdlib>
using namespace std;
// ar1[0..m-1] and ar2[0..n-1] are two given sorted arrays
// and x is given number. This function prints the pair from
// both arrays such that the sum of the pair is closest to x.
void printClosest(int ar1[], int ar2[], int m, int n, int x)
{
// Initialize the diff between pair sum and x.
int diff = INT_MAX;
// res_l and res_r are result indexes from ar1[] and ar2[]
// respectively
int res_l, res_r;
// Start from left side of ar1[] and right side of ar2[]
int l = 0, r = n-1;
while (l<m && r>=0)
{
// If this pair is closer to x than the previously
// found closest, then update res_l, res_r and diff
if (abs(ar1[l] + ar2[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = abs(ar1[l] + ar2[r] - x);
}
// If sum of this pair is more than x, move to smaller
// side
if (ar1[l] + ar2[r] > x)
r--;
else // move to the greater side
l++;
}
// Print the result
cout << "The closest pair is [" << ar1[res_l] << ", "
<< ar2[res_r] << "] \n";
}
// Driver program to test above functions
int main()
{
int ar1[] = {1, 4, 5, 7};
int ar2[] = {10, 20, 30, 40};
int m = sizeof(ar1)/sizeof(ar1[0]);
int n = sizeof(ar2)/sizeof(ar2[0]);
int x = 38;
printClosest(ar1, ar2, m, n, x);
return 0;
}
Java
// Java program to find closest pair in an array
class ClosestPair
{
// ar1[0..m-1] and ar2[0..n-1] are two given sorted
// arrays/ and x is given number. This function prints
// the pair from both arrays such that the sum of the
// pair is closest to x.
void printClosest(int ar1[], int ar2[], int m, int n, int x)
{
// Initialize the diff between pair sum and x.
int diff = Integer.MAX_VALUE;
// res_l and res_r are result indexes from ar1[] and ar2[]
// respectively
int res_l = 0, res_r = 0;
// Start from left side of ar1[] and right side of ar2[]
int l = 0, r = n-1;
while (l<m && r>=0)
{
// If this pair is closer to x than the previously
// found closest, then update res_l, res_r and diff
if (Math.abs(ar1[l] + ar2[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = Math.abs(ar1[l] + ar2[r] - x);
}
// If sum of this pair is more than x, move to smaller
// side
if (ar1[l] + ar2[r] > x)
r--;
else // move to the greater side
l++;
}
// Print the result
System.out.print("The closest pair is [" + ar1[res_l] +
", " + ar2[res_r] + "]");
}
// Driver program to test above functions
public static void main(String args[])
{
ClosestPair ob = new ClosestPair();
int ar1[] = {1, 4, 5, 7};
int ar2[] = {10, 20, 30, 40};
int m = ar1.length;
int n = ar2.length;
int x = 38;
ob.printClosest(ar1, ar2, m, n, x);
}
}
/*This code is contributed by Rajat Mishra */
Python3
# Python3 program to find the pair from
# two sorted arrays such that the sum
# of pair is closest to a given number x
import sys
# ar1[0..m-1] and ar2[0..n-1] are two
# given sorted arrays and x is given
# number. This function prints the pair
# from both arrays such that the sum
# of the pair is closest to x.
def printClosest(ar1, ar2, m, n, x):
# Initialize the diff between
# pair sum and x.
diff=sys.maxsize
# res_l and res_r are result
# indexes from ar1[] and ar2[]
# respectively. Start from left
# side of ar1[] and right side of ar2[]
l = 0
r = n-1
while(l < m and r >= 0):
# If this pair is closer to x than
# the previously found closest,
# then update res_l, res_r and diff
if abs(ar1[l] + ar2[r] - x) < diff:
res_l = l
res_r = r
diff = abs(ar1[l] + ar2[r] - x)
# If sum of this pair is more than x,
# move to smaller side
if ar1[l] + ar2[r] > x:
r=r-1
else: # move to the greater side
l=l+1
# Print the result
print("The closest pair is [",
ar1[res_l],",",ar2[res_r],"]")
# Driver program to test above functions
ar1 = [1, 4, 5, 7]
ar2 = [10, 20, 30, 40]
m = len(ar1)
n = len(ar2)
x = 38
printClosest(ar1, ar2, m, n, x)
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to find closest pair in
// an array
using System;
class GFG {
// ar1[0..m-1] and ar2[0..n-1] are two
// given sorted arrays/ and x is given
// number. This function prints the
// pair from both arrays such that the
// sum of the pair is closest to x.
static void printClosest(int []ar1,
int []ar2, int m, int n, int x)
{
// Initialize the diff between pair
// sum and x.
int diff = int.MaxValue;
// res_l and res_r are result
// indexes from ar1[] and ar2[]
// respectively
int res_l = 0, res_r = 0;
// Start from left side of ar1[]
// and right side of ar2[]
int l = 0, r = n-1;
while (l < m && r >= 0)
{
// If this pair is closer to
// x than the previously
// found closest, then update
// res_l, res_r and diff
if (Math.Abs(ar1[l] +
ar2[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = Math.Abs(ar1[l]
+ ar2[r] - x);
}
// If sum of this pair is more
// than x, move to smaller
// side
if (ar1[l] + ar2[r] > x)
r--;
else // move to the greater side
l++;
}
// Print the result
Console.Write("The closest pair is ["
+ ar1[res_l] + ", "
+ ar2[res_r] + "]");
}
// Driver program to test above functions
public static void Main()
{
int []ar1 = {1, 4, 5, 7};
int []ar2 = {10, 20, 30, 40};
int m = ar1.Length;
int n = ar2.Length;
int x = 38;
printClosest(ar1, ar2, m, n, x);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find the pair
// from two sorted arrays such
// that the sum of pair is
// closest to a given number x
// ar1[0..m-1] and ar2[0..n-1]
// are two given sorted arrays
// and x is given number. This
// function prints the pair from
// both arrays such that the sum
// of the pair is closest to x.
function printClosest($ar1, $ar2,
$m, $n, $x)
{
// Initialize the diff between
// pair sum and x.
$diff = PHP_INT_MAX;
// res_l and res_r are result
// indexes from ar1[] and ar2[]
// respectively
$res_l;
$res_r;
// Start from left side of
// ar1[] and right side of ar2[]
$l = 0;
$r = $n - 1;
while ($l < $m and $r >= 0)
{
// If this pair is closer to
// x than the previously
// found closest, then
// update res_l, res_r and
// diff
if (abs($ar1[$l] + $ar2[$r] -
$x) < $diff)
{
$res_l = $l;
$res_r = $r;
$diff = abs($ar1[$l] +
$ar2[$r] - $x);
}
// If sum of this pair is
// more than x, move to smaller
// side
if ($ar1[$l] + $ar2[$r] > $x)
$r--;
// move to the greater side
else
$l++;
}
// Print the result
echo "The closest pair is [" , $ar1[$res_l] , ", "
, $ar2[$res_r] , "] \n";
}
// Driver Code
$ar1 = array(1, 4, 5, 7);
$ar2 = array(10, 20, 30, 40);
$m = count($ar1);
$n = count($ar2);
$x = 38;
printClosest($ar1, $ar2, $m, $n, $x);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find
// the pair from two sorted arrays such
// that the sum of pair is closest
// to a given number x
// ar1[0..m-1] and ar2[0..n-1] are
// two given sorted arrays
// and x is given number.
// This function prints the pair
// from both arrays such that the
// sum of the pair is closest to x.
function printClosest( ar1, ar2, m, n, x)
{
// Initialize the diff
// between pair sum and x.
let diff = Number.MAX_VALUE;
// res_l and res_r are result
// indexes from ar1[] and ar2[]
// respectively
let res_l, res_r;
// Start from left side of ar1[] and
// right side of ar2[]
let l = 0, r = n-1;
while (l<m && r>=0)
{
// If this pair is closer to
// x than the previously
// found closest, then update
// res_l, res_r and diff
if (Math.abs(ar1[l] + ar2[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = Math.abs(ar1[l] + ar2[r] - x);
}
// If sum of this pair is more than x,
// move to smaller side
if (ar1[l] + ar2[r] > x)
r--;
else // move to the greater side
l++;
}
// Print the result
document.write("The closest pair is [" + ar1[res_l] + ", "
+ ar2[res_r] + "] </br>");
}
// driver code
let ar1 = [1, 4, 5, 7];
let ar2 = [10, 20, 30, 40];
let m = ar1.length;
let n = ar2.length;
let x = 38;
printClosest(ar1, ar2, m, n, x);
</script>
Producción:
The closest pair is [7, 30]
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Par de valores de diferencia más pequeña entre dos arrays no ordenadas
Este artículo es una contribución de Harsh. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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