Dadas tres arrays ordenadas A[], B[] y C[], encuentre 3 elementos i, j y k de A, B y C respectivamente tales que max(abs(A[i] – B[j]), abs( B[j] – C[k]), abs(C[k] – A[i])) se minimiza. Aquí abs() indica valor absoluto.
Ejemplo :
Input: A[] = {1, 4, 10}
B[] = {2, 15, 20}
C[] = {10, 12}
Output: 10 15 10
10 from A, 15 from B and 10 from C
Input: A[] = {20, 24, 100}
B[] = {2, 19, 22, 79, 800}
C[] = {10, 12, 23, 24, 119}
Output: 24 22 23
24 from A, 22 from B and 23 from C
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Una solución simple es ejecutar tres bucles anidados para considerar todos los tripletes de A, B y C. Calcular el valor de max(abs(A[i] – B[j]), abs(B[j] – C[k] ), abs(C[k] – A[i])) para cada triplete y devolver el mínimo de todos los valores. La complejidad temporal de esta solución es O(n 3 )
Una mejor solución es utilizar la búsqueda binaria.
1) Iterar sobre todos los elementos de A[],
a) Búsqueda binaria del elemento menor o igual que en B[] y C[], y observar la diferencia.
2) Repita el paso 1 para B[] y C[].
3) Retorno mínimo global.
La complejidad temporal de esta solución es O(nLogn)
Solución eficiente Sea ‘p’ el tamaño de A[], ‘q’ el tamaño de B[] y ‘r’ el tamaño de C[]
1) Start with i=0, j=0 and k=0 (Three index variables for A,
B and C respectively)
// p, q and r are sizes of A[], B[] and C[] respectively.
2) Do following while i < p and j < q and k < r
a) Find min and maximum of A[i], B[j] and C[k]
b) Compute diff = max(X, Y, Z) - min(A[i], B[j], C[k]).
c) If new result is less than current result, change
it to the new result.
d) Increment the pointer of the array which contains
the minimum.
Tenga en cuenta que incrementamos el puntero de la array que tiene el mínimo porque nuestro objetivo es disminuir la diferencia. Aumentar el puntero máximo aumenta la diferencia. Aumentar el segundo puntero máximo puede aumentar potencialmente la diferencia.
C++
// C++ program to find 3 elements such that max(abs(A[i]-B[j]), abs(B[j]-
// C[k]), abs(C[k]-A[i])) is minimized.
#include<bits/stdc++.h>
using namespace std;
void findClosest(int A[], int B[], int C[], int p, int q, int r)
{
int diff = INT_MAX; // Initialize min diff
// Initialize result
int res_i =0, res_j = 0, res_k = 0;
// Traverse arrays
int i=0,j=0,k=0;
while (i < p && j < q && k < r)
{
// Find minimum and maximum of current three elements
int minimum = min(A[i], min(B[j], C[k]));
int maximum = max(A[i], max(B[j], C[k]));
// Update result if current diff is less than the min
// diff so far
if (maximum-minimum < diff)
{
res_i = i, res_j = j, res_k = k;
diff = maximum - minimum;
}
// We can't get less than 0 as values are absolute
if (diff == 0) break;
// Increment index of array with smallest value
if (A[i] == minimum) i++;
else if (B[j] == minimum) j++;
else k++;
}
// Print result
cout << A[res_i] << " " << B[res_j] << " " << C[res_k];
}
// Driver program
int main()
{
int A[] = {1, 4, 10};
int B[] = {2, 15, 20};
int C[] = {10, 12};
int p = sizeof A / sizeof A[0];
int q = sizeof B / sizeof B[0];
int r = sizeof C / sizeof C[0];
findClosest(A, B, C, p, q, r);
return 0;
}
Java
// Java program to find 3 elements such
// that max(abs(A[i]-B[j]), abs(B[j]-C[k]),
// abs(C[k]-A[i])) is minimized.
import java.io.*;
class GFG {
static void findClosest(int A[], int B[], int C[],
int p, int q, int r)
{
int diff = Integer.MAX_VALUE; // Initialize min diff
// Initialize result
int res_i =0, res_j = 0, res_k = 0;
// Traverse arrays
int i = 0, j = 0, k = 0;
while (i < p && j < q && k < r)
{
// Find minimum and maximum of current three elements
int minimum = Math.min(A[i],
Math.min(B[j], C[k]));
int maximum = Math.max(A[i],
Math.max(B[j], C[k]));
// Update result if current diff is
// less than the min diff so far
if (maximum-minimum < diff)
{
res_i = i;
res_j = j;
res_k = k;
diff = maximum - minimum;
}
// We can't get less than 0
// as values are absolute
if (diff == 0) break;
// Increment index of array
// with smallest value
if (A[i] == minimum) i++;
else if (B[j] == minimum) j++;
else k++;
}
// Print result
System.out.println(A[res_i] + " " +
B[res_j] + " " + C[res_k]);
}
// Driver code
public static void main (String[] args)
{
int A[] = {1, 4, 10};
int B[] = {2, 15, 20};
int C[] = {10, 12};
int p = A.length;
int q = B.length;
int r = C.length;
// Function calling
findClosest(A, B, C, p, q, r);
}
}
// This code is contributed by Ajit.
Python3
# Python program to find 3 elements such # that max(abs(A[i]-B[j]), abs(B[j]- C[k]), # abs(C[k]-A[i])) is minimized. import sys def findCloset(A, B, C, p, q, r): # Initialize min diff diff = sys.maxsize res_i = 0 res_j = 0 res_k = 0 # Traverse Array i = 0 j = 0 k = 0 while(i < p and j < q and k < r): # Find minimum and maximum of # current three elements minimum = min(A[i], min(B[j], C[k])) maximum = max(A[i], max(B[j], C[k])); # Update result if current diff is # less than the min diff so far if maximum-minimum < diff: res_i = i res_j = j res_k = k diff = maximum - minimum; # We can 't get less than 0 as # values are absolute if diff == 0: break # Increment index of array with # smallest value if A[i] == minimum: i = i+1 elif B[j] == minimum: j = j+1 else: k = k+1 # Print result print(A[res_i], " ", B[res_j], " ", C[res_k]) # Driver Program A = [1, 4, 10] B = [2, 15, 20] C = [10, 12] p = len(A) q = len(B) r = len(C) findCloset(A,B,C,p,q,r) # This code is contributed by Shrikant13.
C#
// C# program to find 3 elements
// such that max(abs(A[i]-B[j]),
// abs(B[j]-C[k]), abs(C[k]-A[i]))
// is minimized.
using System;
class GFG
{
static void findClosest(int []A, int []B,
int []C, int p,
int q, int r)
{
// Initialize min diff
int diff = int.MaxValue;
// Initialize result
int res_i = 0,
res_j = 0,
res_k = 0;
// Traverse arrays
int i = 0, j = 0, k = 0;
while (i < p && j < q && k < r)
{
// Find minimum and maximum
// of current three elements
int minimum = Math.Min(A[i],
Math.Min(B[j], C[k]));
int maximum = Math.Max(A[i],
Math.Max(B[j], C[k]));
// Update result if current
// diff is less than the min
// diff so far
if (maximum - minimum < diff)
{
res_i = i;
res_j = j;
res_k = k;
diff = maximum - minimum;
}
// We can't get less than 0
// as values are absolute
if (diff == 0) break;
// Increment index of array
// with smallest value
if (A[i] == minimum) i++;
else if (B[j] == minimum) j++;
else k++;
}
// Print result
Console.WriteLine(A[res_i] + " " +
B[res_j] + " " +
C[res_k]);
}
// Driver code
public static void Main ()
{
int []A = {1, 4, 10};
int []B = {2, 15, 20};
int []C = {10, 12};
int p = A.Length;
int q = B.Length;
int r = C.Length;
// Function calling
findClosest(A, B, C, p, q, r);
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP program to find 3 elements such
// that max(abs(A[i]-B[j]), abs(B[j]-
// C[k]), abs(C[k]-A[i])) is minimized.
function findClosest($A, $B, $C, $p, $q, $r)
{
$diff = PHP_INT_MAX; // Initialize min diff
// Initialize result
$res_i = 0;
$res_j = 0;
$res_k = 0;
// Traverse arrays
$i = 0;
$j = 0;
$k = 0;
while ($i < $p && $j < $q && $k < $r)
{
// Find minimum and maximum of
// current three elements
$minimum = min($A[$i], min($B[$j], $C[$k]));
$maximum = max($A[$i], max($B[$j], $C[$k]));
// Update result if current diff is
// less than the min diff so far
if ($maximum-$minimum < $diff)
{
$res_i = $i; $res_j = $j; $res_k = $k;
$diff = $maximum - $minimum;
}
// We can't get less than 0 as
// values are absolute
if ($diff == 0) break;
// Increment index of array with
// smallest value
if ($A[$i] == $minimum) $i++;
else if ($B[$j] == $minimum) $j++;
else $k++;
}
// Print result
echo $A[$res_i] , " ", $B[$res_j],
" ", $C[$res_k];
}
// Driver Code
$A = array(1, 4, 10);
$B = array(2, 15, 20);
$C = array(10, 12);
$p = sizeof($A);
$q = sizeof($B);
$r = sizeof($C);
findClosest($A, $B, $C, $p, $q, $r);
// This code is contributed by Sach_Code
?>
Javascript
<script>
// JavaScript program to find 3 elements
// such that max(abs(A[i]-B[j]), abs(B[j]-
// C[k]), abs(C[k]-A[i])) is minimized.
function findClosest(A, B, C, p, q, r)
{
var diff = Math.pow(10, 9); // Initialize min diff
// Initialize result
var res_i = 0,
res_j = 0,
res_k = 0;
// Traverse arrays
var i = 0,
j = 0,
k = 0;
while (i < p && j < q && k < r)
{
// Find minimum and maximum of current three elements
var minimum = Math.min(A[i], Math.min(B[j], C[k]));
var maximum = Math.max(A[i], Math.max(B[j], C[k]));
// Update result if current diff is less than the min
// diff so far
if (maximum - minimum < diff)
{
(res_i = i), (res_j = j), (res_k = k);
diff = maximum - minimum;
}
// We can't get less than 0 as values are absolute
if (diff == 0) break;
// Increment index of array with smallest value
if (A[i] == minimum)
i++;
else if (B[j] == minimum)
j++;
else
k++;
}
// Print result
document.write(A[res_i] + " " + B[res_j] + " " + C[res_k]);
}
// Driver program
var A = [1, 4, 10];
var B = [2, 15, 20];
var C = [10, 12];
var p = A.length;
var q = B.length;
var r = C.length;
findClosest(A, B, C, p, q, r);
// This code is contributed by rdtank.
</script>
Producción:
10 15 10
La complejidad temporal de esta solución es O(p + q + r) donde p, q y r son tamaños de A[], B[] y C[] respectivamente.
Gracias a Gaurav Ahirwar por sugerir las soluciones anteriores.
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