Eliminación eficiente de duplicados en arrays Java

Eliminar eficientemente elementos duplicados de un array es una tarea fundamental en programación. Este artículo explora tres enfoques distintos en Java, cada uno ofreciendo un equilibrio diferente entre velocidad y uso de memoria. Comprender estas compensaciones es crucial para seleccionar el método óptimo para su aplicación específica.

Tabla de Contenido

• Usando un Array Temporal
• Usando un Índice Separado
• Usando el método Arrays.sort()
• Comparación de Métodos

Usando un Array Temporal

Este método sencillo itera a través del array de entrada. Cada elemento se compara con un array temporal que contiene solo los elementos únicos encontrados hasta el momento. Si un elemento no se encuentra en el array temporal, se agrega. Si bien es fácil de entender, su estructura de bucle anidado lleva a una complejidad de tiempo de O(n²), lo que lo hace ineficiente para arrays grandes.

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesTempArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0]; 
        }

        int[] uniqueArr = new int[arr.length]; 
        int uniqueCount = 0;

        for (int i = 0; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < uniqueCount; j++) {
                if (arr[i] == uniqueArr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount); 
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 4, 4, 5, 5, 5};
        int[] uniqueArr = removeDuplicatesTempArray(arr);
        System.out.println("Array original: " + Arrays.toString(arr));
        System.out.println("Array con duplicados eliminados: " + Arrays.toString(uniqueArr));
    }
}

Complejidad de Tiempo: O(n²)
Complejidad de Espacio: O(n)

Usando un Índice Separado

Este método mejora la eficiencia del espacio modificando el array original en su lugar. Utiliza un índice separado para rastrear la posición del siguiente elemento único. Se itera el array y los elementos únicos se mueven a las posiciones indicadas por este índice. Si bien es eficiente en espacio (O(1)), todavía sufre de una complejidad de tiempo O(n²) debido a los bucles anidados.

public class RemoveDuplicates {

    public static int[] removeDuplicatesIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        int index = 1; 
        for (int i = 1; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < index; j++) {
                if (arr[i] == arr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                arr[index++] = arr[i];
            }
        }
        return Arrays.copyOf(arr, index);
    }
    //el método main permanece igual que el anterior
}

Complejidad de Tiempo: O(n²)
Complejidad de Espacio: O(1)

Usando el método Arrays.sort()

Este enfoque aprovecha la funcionalidad de ordenamiento incorporada de Java. Ordenar el array primero junta los elementos duplicados. Una pasada posterior a través del array ordenado identifica y retiene solo la primera ocurrencia de cada elemento. La complejidad del tiempo está dominada por el algoritmo de ordenamiento (O(n log n)), ofreciendo un rendimiento significativamente mejor para conjuntos de datos más grandes que los métodos anteriores.

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        Arrays.sort(arr); 
        int[] uniqueArr = new int[arr.length];
        uniqueArr[0] = arr[0]; 
        int uniqueCount = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1]) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount);
    }
    //el método main permanece igual que el anterior
}

Complejidad de Tiempo: O(n log n)
Complejidad de Espacio: O(n)

Comparación de Métodos

La elección del método depende del tamaño de sus datos y sus prioridades. Para arrays más pequeños, la simplicidad del método de array temporal podría ser suficiente. Para arrays más grandes, las ganancias de rendimiento del método Arrays.sort() superan su complejidad de espacio ligeramente mayor. El método de índice separado ofrece una solución eficiente en espacio, pero su complejidad de tiempo cuadrática lo hace menos atractivo para conjuntos de datos grandes.