Dadas dos arrays de enteros, calcule el par de valores (un valor en cada array) con la diferencia más pequeña (no negativa). Devolver la diferencia.
Ejemplos:
Input : A[] = {l, 3, 15, 11, 2}
B[] = {23, 127, 235, 19, 8}
Output : 3
That is, the pair (11, 8)
Input : A[] = {l0, 5, 40}
B[] = {50, 90, 80}
Output : 10
That is, the pair (40, 50)
Una solución simple es Fuerza bruta usando dos bucles con Complejidad de tiempo O(n 2 ) .
Una mejor solución es ordenar las arrays. Una vez que se ordenan las arrays, podemos encontrar la diferencia mínima iterando a través de las arrays utilizando el enfoque que se describe en la publicación a continuación.
Encuentre el par más cercano de dos arrays ordenadas
Considere las siguientes dos arrays:
- R: {l, 2, 11, 15}
- B: {4, 12, 19, 23, 127, 235}
- Suponga que un puntero a apunta al comienzo de A y un puntero b apunta al comienzo de B. La diferencia actual entre ay bis 3. Almacene esto como el min.
- ¿Cómo podemos (potencialmente) hacer que esta diferencia sea más pequeña? Bueno, el valor en bis es mayor que el valor en a, por lo que mover b solo hará que la diferencia sea mayor. Por lo tanto, queremos mover a.
- Ahora a apunta a 2 yb (todavía) apunta a 4. Esta diferencia es 2, por lo que debemos actualizar min. Mueve a, ya que es más pequeño.
- Ahora a apunta a 11 yb apunta a 4. Mueve b.
- Ahora a apunta a 11 yb apunta a 12. Actualice min a 1. Mueva b. Y así.
A continuación se muestra la implementación de la idea.
C++
// C++ Code to find Smallest
// Difference between two Arrays
#include <bits/stdc++.h>
using namespace std;
// function to calculate Small
// result between two arrays
int findSmallestDifference(int A[], int B[],
int m, int n)
{
// Sort both arrays using
// sort function
sort(A, A + m);
sort(B, B + n);
int a = 0, b = 0;
// Initialize result as max value
int result = INT_MAX;
// Scan Both Arrays upto
// sizeof of the Arrays
while (a < m && b < n)
{
if (abs(A[a] - B[b]) < result)
result = abs(A[a] - B[b]);
// Move Smaller Value
if (A[a] < B[b])
a++;
else
b++;
}
// return final sma result
return result;
}
// Driver Code
int main()
{
// Input given array A
int A[] = {1, 2, 11, 5};
// Input given array B
int B[] = {4, 12, 19, 23, 127, 235};
// Calculate size of Both arrays
int m = sizeof(A) / sizeof(A[0]);
int n = sizeof(B) / sizeof(B[0]);
// Call function to print
// smallest result
cout << findSmallestDifference(A, B, m, n);
return 0;
}
Java
// Java Code to find Smallest
// Difference between two Arrays
import java.util.*;
class GFG
{
// function to calculate Small
// result between two arrays
static int findSmallestDifference(int A[], int B[],
int m, int n)
{
// Sort both arrays
// using sort function
Arrays.sort(A);
Arrays.sort(B);
int a = 0, b = 0;
// Initialize result as max value
int result = Integer.MAX_VALUE;
// Scan Both Arrays upto
// sizeof of the Arrays
while (a < m && b < n)
{
if (Math.abs(A[a] - B[b]) < result)
result = Math.abs(A[a] - B[b]);
// Move Smaller Value
if (A[a] < B[b])
a++;
else
b++;
}
// return final sma result
return result;
}
// Driver Code
public static void main(String[] args)
{
// Input given array A
int A[] = {1, 2, 11, 5};
// Input given array B
int B[] = {4, 12, 19, 23, 127, 235};
// Calculate size of Both arrays
int m = A.length;
int n = B.length;
// Call function to
// print smallest result
System.out.println(findSmallestDifference
(A, B, m, n));
}
}
// This code is contributed
// by Arnav Kr. Mandal.
Python3
# Python 3 Code to find # Smallest Difference between # two Arrays import sys # function to calculate # Small result between # two arrays def findSmallestDifference(A, B, m, n): # Sort both arrays # using sort function A.sort() B.sort() a = 0 b = 0 # Initialize result as max value result = sys.maxsize # Scan Both Arrays upto # sizeof of the Arrays while (a < m and b < n): if (abs(A[a] - B[b]) < result): result = abs(A[a] - B[b]) # Move Smaller Value if (A[a] < B[b]): a += 1 else: b += 1 # return final sma result return result # Driver Code # Input given array A A = [1, 2, 11, 5] # Input given array B B = [4, 12, 19, 23, 127, 235] # Calculate size of Both arrays m = len(A) n = len(B) # Call function to # print smallest result print(findSmallestDifference(A, B, m, n)) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# Code to find Smallest
// Difference between two Arrays
using System;
class GFG
{
// function to calculate Small
// result between two arrays
static int findSmallestDifference(int []A, int []B,
int m, int n)
{
// Sort both arrays using
// sort function
Array.Sort(A);
Array.Sort(B);
int a = 0, b = 0;
// Initialize result as max value
int result = int.MaxValue;
// Scan Both Arrays upto
// sizeof of the Arrays
while (a < m && b < n)
{
if (Math.Abs(A[a] - B[b]) < result)
result = Math.Abs(A[a] - B[b]);
// Move Smaller Value
if (A[a] < B[b])
a++;
else
b++;
}
// return final sma result
return result;
}
// Driver Code
public static void Main()
{
// Input given array A
int []A = {1, 2, 11, 5};
// Input given array B
int []B = {4, 12, 19, 23, 127, 235};
// Calculate size of Both arrays
int m = A.Length;
int n = B.Length;
// Call function to
// print smallest result
Console.Write(findSmallestDifference
(A, B, m, n));
}
}
// This code is contributed
// by nitin mittal.
PHP
<?php
// PHP Code to find Smallest
// Difference between two Arrays
// function to calculate Small
// result between two arrays
function findSmallestDifference($A, $B,
$m, $n)
{
// Sort both arrays
// using sort function
sort($A);
sort($A, $m);
sort($B);
sort($B, $n);
$a = 0; $b = 0;
$INT_MAX = 1;
// Initialize result
// as max value
$result = $INT_MAX;
// Scan Both Arrays upto
// sizeof of the Arrays
while ($a < $m && $b < $n)
{
if (abs($A[$a] - $B[$b]) < $result)
$result = abs($A[$a] - $B[$b]);
// Move Smaller Value
if ($A[$a] < $B[$b])
$a++;
else
$b++;
}
// return final sma result
return $result;
}
// Driver Code
{
// Input given array A
$A = array(1, 2, 11, 5);
// Input given array B
$B = array(4, 12, 19, 23, 127, 235);
// Calculate size of Both arrays
$m = sizeof($A) / sizeof($A[0]);
$n = sizeof($B) / sizeof($B[0]);
// Call function to print
// smallest result
echo findSmallestDifference($A, $B, $m, $n);
return 0;
}
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript Code to find Smallest
// Difference between two Arrays
// function to calculate Small
// result between two arrays
function findSmallestDifference(A, B, m, n)
{
// Sort both arrays using
// sort function
A.sort((a, b) => a - b);
B.sort((a, b) => a - b);
let a = 0, b = 0;
// Initialize result as max value
let result = Number.MAX_SAFE_INTEGER;
// Scan Both Arrays upto
// sizeof of the Arrays
while (a < m && b < n)
{
if (Math.abs(A[a] - B[b]) < result)
result = Math.abs(A[a] - B[b]);
// Move Smaller Value
if (A[a] < B[b])
a++;
else
b++;
}
// Return final sma result
return result;
}
// Driver Code
// Input given array A
let A = [ 1, 2, 11, 5 ];
// Input given array B
let B = [ 4, 12, 19, 23, 127, 235 ];
// Calculate size of Both arrays
let m = A.length;
let n = B.length;
// Call function to print
// smallest result
document.write(findSmallestDifference(
A, B, m, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción
1
Este algoritmo toma O(m log m + n log n) tiempo para ordenar y O(m + n) tiempo para encontrar la diferencia mínima. Por lo tanto, el tiempo de ejecución general es O(m log m + n log n).
Espacio Auxiliar: O(1)
Este artículo es una contribución del Sr. Somesh Awasthi . 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