Remoção Eficiente de Duplicatas em Arrays Java

Remover eficientemente elementos duplicados de um array é uma tarefa fundamental na programação. Este artigo explora três abordagens distintas em Java, cada uma oferecendo um equilíbrio diferente entre velocidade e uso de memória. Entender essas compensações é crucial para selecionar o método ideal para sua aplicação específica.

Sumário

• Usando um Array Temporário
• Usando um Índice Separado
• Usando o método Arrays.sort()
• Comparação de Métodos

Usando um Array Temporário

Este método direto itera pelo array de entrada. Cada elemento é verificado contra um array temporário contendo apenas elementos únicos encontrados até o momento. Se um elemento não for encontrado no array temporário, ele é adicionado. Embora fácil de entender, sua estrutura de loop aninhado leva a uma complexidade de tempo de O(n²), tornando-o 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 com duplicatas removidas: " + Arrays.toString(uniqueArr));
    }
}

Complexidade de Tempo: O(n²)
Complexidade de Espaço: O(n)

Usando um Índice Separado

Este método melhora a eficiência de espaço modificando o array original no local. Ele usa um índice separado para rastrear a posição do próximo elemento único. O array é iterado, e elementos únicos são movidos para as posições indicadas por este índice. Embora eficiente em espaço (O(1)), ainda sofre com complexidade de tempo O(n²) devido aos loops aninhados.

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);
    }
    //o método main permanece o mesmo que acima
}

Complexidade de Tempo: O(n²)
Complexidade de Espaço: O(1)

Usando o método Arrays.sort()

Esta abordagem utiliza a funcionalidade de classificação integrada do Java. Classificar o array primeiro aproxima elementos duplicados. Uma passagem subsequente única pelo array classificado identifica e retém apenas a primeira ocorrência de cada elemento. A complexidade de tempo é dominada pelo algoritmo de classificação (O(n log n)), oferecendo desempenho significativamente melhor para conjuntos de dados maiores do que os 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);
    }
    //o método main permanece o mesmo que acima
}

Complexidade de Tempo: O(n log n)
Complexidade de Espaço: O(n)

Comparação de Métodos

A escolha do método depende do tamanho dos seus dados e suas prioridades. Para arrays menores, a simplicidade do método de array temporário pode ser suficiente. Para arrays maiores, os ganhos de desempenho do método Arrays.sort() superam sua complexidade de espaço ligeiramente maior. O método de índice separado oferece uma solução eficiente em espaço, mas sua complexidade de tempo quadrática o torna menos atraente para conjuntos de dados grandes.