Effiziente Entfernung von Duplikaten aus Java-Arrays

Das effiziente Entfernen von Duplikaten aus einem Array ist eine grundlegende Aufgabe in der Programmierung. Dieser Artikel untersucht drei verschiedene Java-Ansätze, die jeweils einen unterschiedlichen Ausgleich zwischen Geschwindigkeit und Speicherverbrauch bieten. Das Verständnis dieser Kompromisse ist entscheidend für die Auswahl der optimalen Methode für Ihre spezifische Anwendung.

Inhaltsverzeichnis

• Verwendung eines temporären Arrays
• Verwendung eines separaten Index
• Verwendung der Arrays.sort() Methode
• Methodenvergleich

Verwendung eines temporären Arrays

Diese einfache Methode iteriert durch das Eingabearray. Jedes Element wird mit einem temporären Array verglichen, das nur die bisher gefundenen eindeutigen Elemente enthält. Wenn ein Element nicht im temporären Array gefunden wird, wird es hinzugefügt. Obwohl leicht verständlich, führt seine verschachtelte Schleifenstruktur zu einer Zeitkomplexität von O(n²), was sie für große Arrays ineffizient macht.

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("Original array: " + Arrays.toString(arr));
        System.out.println("Array with duplicates removed: " + Arrays.toString(uniqueArr));
    }
}

Zeitkomplexität: O(n²)
Speicherkomplexität: O(n)

Verwendung eines separaten Index

Diese Methode verbessert die Speichereffizienz, indem sie das ursprüngliche Array direkt verändert. Sie verwendet einen separaten Index, um die Position des nächsten eindeutigen Elements zu verfolgen. Das Array wird iteriert, und eindeutige Elemente werden an die von diesem Index angegebenen Positionen verschoben. Obwohl speichereffizient (O(1)), leidet sie immer noch unter einer Zeitkomplexität von O(n²) aufgrund der verschachtelten Schleifen.

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);
    }
    //main method remains the same as above
}

Zeitkomplexität: O(n²)
Speicherkomplexität: O(1)

Verwendung der Arrays.sort() Methode

Dieser Ansatz nutzt die integrierte Sortierfunktionalität von Java. Das Sortieren des Arrays bringt zunächst Duplikate zusammen. Ein anschließender einzelner Durchlauf durch das sortierte Array identifiziert und behält nur das erste Auftreten jedes Elements bei. Die Zeitkomplexität wird vom Sortieralgorithmus (O(n log n)) dominiert und bietet für größere Datensätze eine deutlich bessere Leistung als die vorherigen Methoden.

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);
    }
    //main method remains the same as above
}

Zeitkomplexität: O(n log n)
Speicherkomplexität: O(n)

Methodenvergleich

Die Wahl der Methode hängt von der Größe Ihrer Daten und Ihren Prioritäten ab. Für kleinere Arrays könnte die Einfachheit der Methode mit dem temporären Array ausreichen. Für größere Arrays überwiegen die Leistungsgewinne der Arrays.sort()-Methode ihre etwas höhere Speicherkomplexität. Die Methode mit dem separaten Index bietet eine speichereffiziente Lösung, aber ihre quadratische Zeitkomplexität macht sie für große Datensätze weniger attraktiv.