Encuentre el valor más cercano para cada elemento en la array

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, 11

Entrada: 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);
    }
}
Producción:

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.

Publicación traducida automáticamente

Artículo escrito por kartik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *