Comment vérifier si un tableau Java contient des éléments dupliqués

Introduction

Dans ce laboratoire (lab), vous apprendrez à vérifier si un tableau (array) a des éléments dupliqués en Java en utilisant différentes approches. Nous commencerons par une méthode de base utilisant des boucles imbriquées, qui offre une compréhension claire du processus de comparaison.

Ensuite, nous explorerons une technique plus efficace utilisant la structure de données HashSet, montrant comment tirer parti des collections Java pour une détection plus rapide des doublons. Enfin, nous examinerons comment trier le tableau (array) peut simplifier le processus d'identification des doublons. À la fin de ce laboratoire (lab), vous disposerez de plusieurs stratégies pour gérer les éléments dupliqués dans les tableaux (arrays) Java.

Skills Graph

Utilisation de boucles imbriquées pour trouver des doublons

Dans cette étape, nous allons explorer une approche de base pour trouver des éléments dupliqués dans un tableau (array) en utilisant des boucles imbriquées en Java. Cette méthode est simple et facile à comprendre, ce qui en fait un bon point de départ pour apprendre la manipulation de tableaux (arrays) et la conception d'algorithmes de base.

Tout d'abord, créons un nouveau fichier Java nommé FindDuplicatesNested.java dans votre répertoire ~/project. Vous pouvez le faire directement dans l'Explorateur de fichiers de l'IDE Web en cliquant avec le bouton droit dans le dossier project et en sélectionnant "Nouveau fichier", puis en tapant le nom.

Maintenant, ouvrez le fichier FindDuplicatesNested.java dans l'Éditeur de code et ajoutez le code Java suivant :

public class FindDuplicatesNested {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        System.out.println("Finding duplicate elements using nested loops:");

        // Use nested loops to compare each element with every other element
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                // If a duplicate is found (elements are equal and not the same element)
                if (numbers[i] == numbers[j]) {
                    System.out.println("Duplicate found: " + numbers[j]);
                }
            }
        }
    }
}

Décortiquons ce code :

• int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3}; : Cette ligne déclare un tableau d'entiers nommé numbers et l'initialise avec certaines valeurs, y compris des doublons.
• for (int i = 0; i < numbers.length; i++) : C'est la boucle externe. Elle parcourt chaque élément du tableau en utilisant un index i.
• for (int j = i + 1; j < numbers.length; j++) : C'est la boucle interne. Pour chaque élément à l'index i, elle parcourt les éléments restants du tableau en commençant par l'élément après l'index i. Cela est important pour éviter de comparer un élément avec lui-même et pour éviter de trouver la même paire de doublons deux fois (par exemple, comparer l'index 1 avec l'index 4 puis l'index 4 avec l'index 1).
• if (numbers[i] == numbers[j]) : Cette condition vérifie si l'élément à l'index i est égal à l'élément à l'index j. Si ils sont égaux, cela signifie que nous avons trouvé un doublon.
• System.out.println("Duplicate found: " + numbers[j]); : Si un doublon est trouvé, cette ligne affiche un message indiquant l'élément dupliqué.

Enregistrez le fichier en appuyant sur Ctrl + S (ou Cmd + S sur macOS).

Maintenant, ouvrez le Terminal en bas de l'IDE Web. Assurez-vous que vous êtes dans le répertoire ~/project. Vous pouvez le confirmer en tapant pwd puis en appuyant sur Entrée. La sortie devrait être /home/labex/project.

Compilez le code Java en utilisant la commande javac :

javac FindDuplicatesNested.java

S'il n'y a pas d'erreurs, la compilation sera réussie et un fichier FindDuplicatesNested.class sera créé dans le répertoire ~/project. Vous pouvez le vérifier en tapant ls puis en appuyant sur Entrée.

Enfin, exécutez le programme Java compilé en utilisant la commande java :

java FindDuplicatesNested

Vous devriez voir la sortie indiquant les éléments dupliqués trouvés par le programme.

Cette approche utilisant des boucles imbriquées fonctionne en comparant chaque paire possible d'éléments dans le tableau. Bien qu'elle soit simple à comprendre, elle peut devenir inefficace pour de très grands tableaux. Dans les étapes suivantes, nous explorerons des méthodes plus efficaces pour trouver des doublons.

Utilisation de HashSet pour une vérification efficace des doublons

Dans l'étape précédente, nous avons utilisé des boucles imbriquées pour trouver des doublons, ce qui est simple mais peut être lent pour de grands tableaux (arrays). Dans cette étape, nous allons apprendre une méthode plus efficace pour trouver des doublons en utilisant un HashSet.

Un HashSet est une collection en Java qui stocke des éléments uniques. Cela signifie que si vous essayez d'ajouter un élément qui est déjà dans le HashSet, l'opération d'ajout échouera (ou plutôt, retournera false). Nous pouvons tirer parti de cette propriété pour détecter efficacement les doublons.

Voici l'idée : nous parcourons le tableau (array), et pour chaque élément, nous essayons de l'ajouter à un HashSet. Si la méthode add() retourne false, cela signifie que l'élément est déjà dans l'ensemble, et donc, c'est un doublon.

Créons un nouveau fichier Java nommé FindDuplicatesHashSet.java dans votre répertoire ~/project.

Ouvrez le fichier FindDuplicatesHashSet.java dans l'Éditeur de code et ajoutez le code Java suivant :

import java.util.HashSet;
import java.util.Set;

public class FindDuplicatesHashSet {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // Create a HashSet to store unique elements
        Set<Integer> uniqueElements = new HashSet<>();

        System.out.println("Finding duplicate elements using HashSet:");

        // Iterate through the array
        for (int number : numbers) {
            // Try to add the element to the HashSet
            // If add() returns false, the element is a duplicate
            if (!uniqueElements.add(number)) {
                System.out.println("Duplicate found: " + number);
            }
        }
    }
}

Examinons les nouvelles parties de ce code :

• import java.util.HashSet; et import java.util.Set; : Ces lignes importent les classes nécessaires pour utiliser HashSet.
• Set<Integer> uniqueElements = new HashSet<>(); : Cette ligne crée un HashSet vide qui stockera des objets Integer. Nous utilisons Set comme type car HashSet implémente l'interface Set.
• for (int number : numbers) : Il s'agit d'une boucle for améliorée (également connue sous le nom de boucle for-each), qui est un moyen pratique de parcourir chaque élément du tableau (array) numbers.
• !uniqueElements.add(number) : C'est la logique principale. uniqueElements.add(number) tente d'ajouter le number actuel au HashSet. Si le nombre est déjà présent, add() retourne false. L'opérateur ! inverse ce résultat, donc la condition if est vraie seulement lorsque add() retourne false, indiquant un doublon.

Enregistrez le fichier (Ctrl + S ou Cmd + S).

Maintenant, compilez le code Java dans le Terminal :

javac FindDuplicatesHashSet.java

Si la compilation réussit, exécutez le programme :

java FindDuplicatesHashSet

Vous devriez voir la sortie listant les éléments dupliqués trouvés en utilisant la méthode HashSet. Remarquez que cette méthode est généralement plus rapide que l'approche utilisant des boucles imbriquées, en particulier pour les grands tableaux (arrays), car l'ajout et la vérification d'éléments dans un HashSet sont très efficaces.

Test avec un tableau trié

Dans cette étape finale, nous allons explorer une autre approche pour trouver des doublons, en particulier lorsque le tableau (array) est trié. Si un tableau est trié, les éléments dupliqués seront toujours adjacents les uns aux autres. Cela permet une méthode très simple et efficace pour trouver des doublons en comparant simplement les éléments adjacents.

Tout d'abord, créons un nouveau fichier Java nommé FindDuplicatesSorted.java dans votre répertoire ~/project.

Ouvrez le fichier FindDuplicatesSorted.java dans l'Éditeur de code et ajoutez le code Java suivant :

import java.util.Arrays;

public class FindDuplicatesSorted {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // First, sort the array
        Arrays.sort(numbers);

        System.out.println("Finding duplicate elements in a sorted array:");

        // Iterate through the sorted array and compare adjacent elements
        for (int i = 0; i < numbers.length - 1; i++) {
            // If the current element is equal to the next element, it's a duplicate
            if (numbers[i] == numbers[i + 1]) {
                System.out.println("Duplicate found: " + numbers[i]);
            }
        }
    }
}

Examinons les parties clés de ce code :

• import java.util.Arrays; : Cette ligne importe la classe Arrays, qui fournit des méthodes utilitaires pour les tableaux (arrays), y compris le tri.
• Arrays.sort(numbers); : Cette ligne trie le tableau (array) numbers par ordre croissant.
• for (int i = 0; i < numbers.length - 1; i++) : Cette boucle parcourt le tableau trié. Nous bouclons jusqu'à numbers.length - 1 car nous comparons l'élément actuel (numbers[i]) avec l'élément suivant (numbers[i + 1]).
• if (numbers[i] == numbers[i + 1]) : Cette condition vérifie si l'élément actuel est égal à l'élément suivant. Si ils sont identiques, cela signifie que nous avons trouvé un doublon.

Enregistrez le fichier (Ctrl + S ou Cmd + S).

Maintenant, compilez le code Java dans le Terminal :

javac FindDuplicatesSorted.java

Si la compilation réussit, exécutez le programme :

java FindDuplicatesSorted

Vous devriez voir la sortie listant les éléments dupliqués trouvés. Remarquez que parce que le tableau est trié, les doublons apparaîtront consécutivement dans la sortie.

Cette méthode est très efficace pour les tableaux triés car elle ne nécessite qu'un seul passage à travers le tableau après le tri. Cependant, l'étape initiale de tri a elle-même un coût en temps, qui dépend de l'algorithme de tri utilisé par Arrays.sort(). Pour les types primitifs comme int, Arrays.sort() de Java utilise un tri rapide à double pivot, qui a une complexité temporelle moyenne de O(n log n).

Vous avez maintenant exploré trois façons différentes de trouver des doublons dans un tableau en Java : en utilisant des boucles imbriquées, en utilisant un HashSet et en utilisant un tableau trié. Chaque méthode a ses propres avantages et inconvénients en termes de simplicité, d'efficacité et de conditions préalables (comme le fait que le tableau soit trié). Comprendre ces différentes approches est précieux pour choisir la méthode la plus adaptée à un problème donné.

Résumé

Dans ce laboratoire (lab), nous avons exploré différentes méthodes pour vérifier si un tableau (array) contient des éléments dupliqués en Java. Nous avons commencé par implémenter une approche simple utilisant des boucles imbriquées, qui consiste à comparer chaque élément avec tous les autres éléments du tableau. Cette méthode, bien que facile à comprendre, a une complexité temporelle de O(n^2), ce qui la rend moins efficace pour les grands tableaux.

Ensuite, nous avons appris à utiliser la structure de données HashSet pour une vérification plus efficace des doublons. En parcourant le tableau et en essayant d'ajouter chaque élément à un HashSet, nous pouvons rapidement déterminer si un élément est un doublon car la méthode add() de HashSet retourne false si l'élément existe déjà. Cette approche offre une complexité temporelle considérablement améliorée, généralement O(n) en moyenne. Enfin, nous avons examiné comment trier d'abord le tableau peut également être utilisé pour trouver des doublons efficacement, car les éléments dupliqués seront adjacents après le tri.