Dada una array de enteros, encuentre el elemento más cercano para cada elemento.
Ejemplos:
Entrada: arr[] = {10, 5, 11, 6, 20, 12}
Salida: 6, -1, 10, 5, 12, 11Entrada: arr[] = {10, 5, 11, 10, 20, 12}
Salida: 5 -1 10 5 12 11
Una solución simple es ejecutar dos bucles anidados. Elegimos un elemento externo uno por uno. Para cada elemento seleccionado, recorremos la array restante y encontramos el elemento más cercano. La complejidad temporal de esta solución es O(n*n)
Una solución eficiente es usar Self Balancing BST (Implementado como se establece en C++ y TreeSet en Java ). En un BST de autoequilibrio, podemos realizar operaciones tanto de inserción como más cercanas en tiempo O (Log n).
// Java program to demonstrate insertions in TreeSet
import java.util.*;
class TreeSetDemo {
public static void closestGreater(int[] arr)
{
if (arr.length == -1) {
System.out.print(-1 + " ");
return;
}
// Insert all array elements into a TreeMap.
// A TreeMap value indicates whether an element
// appears once or more.
TreeMap<Integer, Boolean> tm =
new TreeMap<Integer, Boolean>();
for (int i = 0; i < arr.length; i++) {
// A value "True" means that the key
// appears more than once.
if (tm.containsKey(arr[i]))
tm.put(arr[i], true);
else
tm.put(arr[i], false);
}
// Find smallest greater element for every
// array element
for (int i = 0; i < arr.length; i++) {
// If there are multiple occurrences
if (tm.get(arr[i]) == true)
{
System.out.print(arr[i] + " ");
continue;
}
// If element appears only once
Integer greater = tm.higherKey(arr[i]);
Integer lower = tm.lowerKey(arr[i]);
if (greater == null)
System.out.print(lower + " ");
else if (lower == null)
System.out.print(greater + " ");
else {
int d1 = greater - arr[i];
int d2 = arr[i] - lower;
if (d1 > d2)
System.out.print(lower + " ");
else
System.out.print(greater + " ");
}
}
}
public static void main(String[] args)
{
int[] arr = { 10, 5, 11, 6, 20, 12, 10 };
closestGreater(arr);
}
}
10 6 12 5 12 11 10
Ejercicio: Otra solución eficiente es utilizar la ordenación que también funciona en tiempo O(n Log n). Escriba el algoritmo completo y el código para la solución basada en la clasificación.