Suppression efficace des doublons dans les tableaux Java

Supprimer efficacement les éléments dupliqués d’un tableau est une tâche fondamentale en programmation. Cet article explore trois approches Java distinctes, chacune offrant un équilibre différent entre vitesse et utilisation de la mémoire. Comprendre ces compromis est crucial pour choisir la méthode optimale pour votre application spécifique.

Table des matières

• Utiliser un tableau temporaire
• Utiliser un index séparé
• Utiliser la méthode Arrays.sort()
• Comparaison des méthodes

Utiliser un tableau temporaire

Cette méthode simple itère à travers le tableau d’entrée. Chaque élément est comparé à un tableau temporaire contenant uniquement les éléments uniques rencontrés jusqu’à présent. Si un élément n’est pas trouvé dans le tableau temporaire, il est ajouté. Bien que facile à comprendre, sa structure de boucle imbriquée conduit à une complexité temporelle de O(n²), la rendant inefficace pour les grands tableaux.

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("Tableau original : " + Arrays.toString(arr));
        System.out.println("Tableau sans doublons : " + Arrays.toString(uniqueArr));
    }
}

Complexité temporelle : O(n²)
Complexité spatiale : O(n)

Utiliser un index séparé

Cette méthode améliore l’efficacité spatiale en modifiant le tableau original sur place. Elle utilise un index séparé pour suivre la position du prochain élément unique. Le tableau est itéré, et les éléments uniques sont déplacés vers les positions indiquées par cet index. Bien qu’efficace en termes d’espace (O(1)), elle souffre toujours d’une complexité temporelle de O(n²) en raison des boucles imbriquées.

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);
    }
    //la méthode main reste la même que ci-dessus
}

Complexité temporelle : O(n²)
Complexité spatiale : O(1)

Utiliser la méthode Arrays.sort()

Cette approche exploite les fonctionnalités de tri intégrées de Java. Le tri du tableau rassemble d’abord les éléments dupliqués. Une passe unique ultérieure à travers le tableau trié identifie et conserve uniquement la première occurrence de chaque élément. La complexité temporelle est dominée par l’algorithme de tri (O(n log n)), offrant des performances significativement meilleures pour les grands ensembles de données que les méthodes précédentes.

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);
    }
    //la méthode main reste la même que ci-dessus
}

Complexité temporelle : O(n log n)
Complexité spatiale : O(n)

Comparaison des méthodes

Le choix de la méthode dépend de la taille de vos données et de vos priorités. Pour les petits tableaux, la simplicité de la méthode du tableau temporaire peut suffire. Pour les grands tableaux, les gains de performance de la méthode Arrays.sort() compensent sa complexité spatiale légèrement supérieure. La méthode d’index séparé offre une solution efficace en termes d’espace, mais sa complexité temporelle quadratique la rend moins attrayante pour les grands ensembles de données.