Wie man prüft, ob ein Array in Java doppelte Elemente enthält

Einführung

In diesem Lab lernen Sie, wie Sie in Java auf verschiedene Weise prüfen können, ob ein Array doppelte Elemente enthält. Wir beginnen mit einer grundlegenden Methode, die geschachtelte Schleifen verwendet und ein klares Verständnis des Vergleichsprozesses vermittelt.

Als Nächstes werden wir eine effizientere Technik erkunden, die die Datenstruktur HashSet nutzt und zeigt, wie Sie Java-Sammlungen (Collections) für eine schnellere Duplikatprüfung nutzen können. Abschließend werden wir untersuchen, wie das Sortieren des Arrays den Prozess der Identifizierung von Duplikaten vereinfachen kann. Am Ende dieses Labs verfügen Sie über mehrere Strategien zur Behandlung von doppelten Elementen in Java-Arrays.

Skills Graph

Verwendung von geschachtelten Schleifen zur Erkennung von Duplikaten

In diesem Schritt werden wir einen grundlegenden Ansatz zur Erkennung von doppelten Elementen in einem Array mithilfe von geschachtelten Schleifen in Java untersuchen. Diese Methode ist einfach und leicht zu verstehen, was sie zu einem guten Ausgangspunkt für das Lernen von Array-Manipulation und grundlegender Algorithmus-Entwicklung macht.

Zunächst erstellen wir eine neue Java-Datei mit dem Namen FindDuplicatesNested.java in Ihrem ~/project-Verzeichnis. Sie können dies direkt im WebIDE-Dateiexplorer tun, indem Sie mit der rechten Maustaste auf den project-Ordner klicken und "Neue Datei" auswählen, und dann den Namen eingeben.

Öffnen Sie jetzt die Datei FindDuplicatesNested.java im Code-Editor und fügen Sie den folgenden Java-Code hinzu:

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]);
                }
            }
        }
    }
}

Lassen Sie uns diesen Code analysieren:

• int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};: Diese Zeile deklariert ein ganzzahliges Array namens numbers und initialisiert es mit einigen Werten, einschließlich Duplikaten.
• for (int i = 0; i < numbers.length; i++): Dies ist die äußere Schleife. Sie durchläuft jedes Element des Arrays mithilfe eines Index i.
• for (int j = i + 1; j < numbers.length; j++): Dies ist die innere Schleife. Für jedes Element am Index i durchläuft sie die verbleibenden Elemente des Arrays, beginnend mit dem Element nach Index i. Dies ist wichtig, um ein Element nicht mit sich selbst zu vergleichen und um zu vermeiden, dass dasselbe Paar von Duplikaten zweimal gefunden wird (z. B. Index 1 mit Index 4 und dann Index 4 mit Index 1 vergleichen).
• if (numbers[i] == numbers[j]): Diese Bedingung prüft, ob das Element am Index i gleich dem Element am Index j ist. Wenn sie gleich sind, bedeutet dies, dass wir ein Duplikat gefunden haben.
• System.out.println("Duplicate found: " + numbers[j]);: Wenn ein Duplikat gefunden wird, gibt diese Zeile eine Nachricht aus, die das doppelte Element angibt.

Speichern Sie die Datei, indem Sie Strg + S drücken (oder Cmd + S auf macOS).

Öffnen Sie jetzt das Terminal am unteren Rand des WebIDE. Stellen Sie sicher, dass Sie sich im ~/project-Verzeichnis befinden. Sie können dies bestätigen, indem Sie pwd eingeben und Enter drücken. Die Ausgabe sollte /home/labex/project sein.

Kompilieren Sie den Java-Code mit dem Befehl javac:

javac FindDuplicatesNested.java

Wenn keine Fehler auftreten, wird die Kompilierung erfolgreich abgeschlossen, und eine FindDuplicatesNested.class-Datei wird im ~/project-Verzeichnis erstellt. Sie können dies überprüfen, indem Sie ls eingeben und Enter drücken.

Führen Sie schließlich das kompilierte Java-Programm mit dem Befehl java aus:

java FindDuplicatesNested

Sie sollten die Ausgabe sehen, die die vom Programm gefundenen doppelten Elemente angibt.

Dieser Ansatz mit geschachtelten Schleifen funktioniert, indem er jedes mögliche Paar von Elementen im Array vergleicht. Obwohl er einfach zu verstehen ist, kann er für sehr große Arrays ineffizient werden. In den nächsten Schritten werden wir effizientere Methoden zur Erkennung von Duplikaten untersuchen.

Verwendung von HashSet zur effizienten Duplikatprüfung

Im vorherigen Schritt haben wir geschachtelte Schleifen verwendet, um Duplikate zu finden. Dies ist zwar einfach, kann aber für große Arrays langsam sein. In diesem Schritt lernen wir eine effizientere Methode zur Duplikatfindung mithilfe eines HashSet kennen.

Ein HashSet ist eine Sammlung (Collection) in Java, die einzigartige Elemente speichert. Das bedeutet, dass wenn Sie versuchen, ein Element hinzuzufügen, das bereits im HashSet enthalten ist, der Hinzufüge-Vorgang fehlschlägt (oder genauer gesagt, false zurückgibt). Wir können diese Eigenschaft nutzen, um Duplikate effizient zu erkennen.

Hier ist die Idee: Wir durchlaufen das Array, und für jedes Element versuchen wir, es einem HashSet hinzuzufügen. Wenn die add()-Methode false zurückgibt, bedeutet das, dass das Element bereits im Set enthalten ist und somit ein Duplikat ist.

Erstellen wir eine neue Java-Datei mit dem Namen FindDuplicatesHashSet.java in Ihrem ~/project-Verzeichnis.

Öffnen Sie die Datei FindDuplicatesHashSet.java im Code-Editor und fügen Sie den folgenden Java-Code hinzu:

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);
            }
        }
    }
}

Schauen wir uns die neuen Teile dieses Codes an:

• import java.util.HashSet; und import java.util.Set;: Diese Zeilen importieren die notwendigen Klassen für die Verwendung von HashSet.
• Set<Integer> uniqueElements = new HashSet<>();: Diese Zeile erstellt ein leeres HashSet, das Integer-Objekte speichern wird. Wir verwenden Set als Typ, da HashSet das Set-Interface implementiert.
• for (int number : numbers): Dies ist eine erweiterte for-Schleife (auch als for-each-Schleife bekannt), die eine bequeme Möglichkeit ist, jedes Element des numbers-Arrays zu durchlaufen.
• !uniqueElements.add(number): Dies ist die Kernlogik. uniqueElements.add(number) versucht, die aktuelle number zum HashSet hinzuzufügen. Wenn die Zahl bereits vorhanden ist, gibt add() false zurück. Der !-Operator negiert dieses Ergebnis, sodass die if-Bedingung nur dann wahr ist, wenn add() false zurückgibt, was auf ein Duplikat hinweist.

Speichern Sie die Datei (Strg + S oder Cmd + S).

Jetzt kompilieren Sie den Java-Code im Terminal:

javac FindDuplicatesHashSet.java

Wenn die Kompilierung erfolgreich ist, führen Sie das Programm aus:

java FindDuplicatesHashSet

Sie sollten die Ausgabe sehen, die die mit der HashSet-Methode gefundenen doppelten Elemente auflistet. Beachten Sie, dass diese Methode im Allgemeinen schneller ist als der Ansatz mit geschachtelten Schleifen, insbesondere für größere Arrays, da das Hinzufügen und Prüfen von Elementen in einem HashSet sehr effizient ist.

Test mit sortiertem Array

In diesem letzten Schritt werden wir einen weiteren Ansatz zur Duplikatfindung untersuchen, insbesondere wenn das Array sortiert ist. Wenn ein Array sortiert ist, sind doppelte Elemente immer nebeneinander. Dies ermöglicht eine sehr einfache und effiziente Methode zur Duplikatfindung, indem einfach benachbarte Elemente verglichen werden.

Zunächst erstellen wir eine neue Java-Datei mit dem Namen FindDuplicatesSorted.java in Ihrem ~/project-Verzeichnis.

Öffnen Sie die Datei FindDuplicatesSorted.java im Code-Editor und fügen Sie den folgenden Java-Code hinzu:

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]);
            }
        }
    }
}

Schauen wir uns die wichtigen Teile dieses Codes an:

• import java.util.Arrays;: Diese Zeile importiert die Arrays-Klasse, die Hilfsmethoden für Arrays bereitstellt, einschließlich Sortieren.
• Arrays.sort(numbers);: Diese Zeile sortiert das numbers-Array in aufsteigender Reihenfolge.
• for (int i = 0; i < numbers.length - 1; i++): Diese Schleife durchläuft das sortierte Array. Wir laufen bis numbers.length - 1, weil wir das aktuelle Element (numbers[i]) mit dem nächsten Element (numbers[i + 1]) vergleichen.
• if (numbers[i] == numbers[i + 1]): Diese Bedingung prüft, ob das aktuelle Element gleich dem nächsten Element ist. Wenn sie gleich sind, bedeutet das, dass wir ein Duplikat gefunden haben.

Speichern Sie die Datei (Strg + S oder Cmd + S).

Jetzt kompilieren Sie den Java-Code im Terminal:

javac FindDuplicatesSorted.java

Wenn die Kompilierung erfolgreich ist, führen Sie das Programm aus:

java FindDuplicatesSorted

Sie sollten die Ausgabe sehen, die die gefundenen doppelten Elemente auflistet. Beachten Sie, dass, da das Array sortiert ist, die Duplikate in der Ausgabe nacheinander erscheinen.

Diese Methode ist für sortierte Arrays sehr effizient, da sie nur einen einzigen Durchlauf durch das Array nach dem Sortieren erfordert. Allerdings hat der anfängliche Sortierschritt selbst einen Zeitaufwand, der von dem von Arrays.sort() verwendeten Sortieralgorithmus abhängt. Für primitive Typen wie int verwendet Java's Arrays.sort() einen Dual-Pivot-Quicksort, der eine durchschnittliche Zeitkomplexität von O(n log n) hat.

Sie haben nun drei verschiedene Methoden zur Duplikatfindung in einem Array in Java untersucht: die Verwendung von geschachtelten Schleifen, die Verwendung eines HashSet und die Verwendung eines sortierten Arrays. Jede Methode hat ihre eigenen Vor- und Nachteile in Bezug auf Einfachheit, Effizienz und Anforderungen (z. B. dass das Array sortiert sein muss). Das Verständnis dieser verschiedenen Ansätze ist wertvoll, um die am besten geeignete Methode für ein bestimmtes Problem auszuwählen.

Zusammenfassung

In diesem Lab haben wir verschiedene Methoden untersucht, um zu prüfen, ob ein Array in Java doppelte Elemente enthält. Wir haben begonnen, indem wir einen einfachen Ansatz mit geschachtelten Schleifen implementiert haben, bei dem jedes Element mit jedem anderen Element im Array verglichen wird. Diese Methode, obwohl einfach zu verstehen, hat eine Zeitkomplexität von O(n^2), was sie für große Arrays weniger effizient macht.

Als nächstes haben wir gelernt, wie wir die Datenstruktur HashSet für eine effizientere Duplikatprüfung nutzen können. Indem wir das Array durchlaufen und versuchen, jedes Element einem HashSet hinzuzufügen, können wir schnell feststellen, ob ein Element ein Duplikat ist, da die add()-Methode von HashSet false zurückgibt, wenn das Element bereits existiert. Dieser Ansatz bietet eine deutlich verbesserte Zeitkomplexität, typischerweise im Durchschnitt O(n). Schließlich haben wir betrachtet, wie das Sortieren des Arrays zuerst auch zur effizienten Duplikatfindung genutzt werden kann, da doppelte Elemente nach dem Sortieren nebeneinander liegen.