In diesem Artikel untersuchen wir zwei Methoden zum Entfernen doppelter Elemente aus einem Stapel in Java. Wir vergleichen einen einfachen Ansatz mit verschachtelten Schleifen und eine effizientere Methode mit einem HashSet. Das Ziel besteht darin, zu demonstrieren, wie die Entfernung von Duplikaten optimiert werden kann, und die Leistung jedes Ansatzes zu bewerten.

Problemstellung

Schreiben Sie ein Java-Programm, um das doppelte Element aus dem Stapel zu entfernen.

Eingang

Stack data = initData(10L);

Ausgabe

Unique elements using Naive Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Naive Approach: 18200 nanoseconds

Unique elements using Optimized Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Optimized Approach: 34800 nanoseconds

Um Duplikate aus einem bestimmten Stapel zu entfernen, haben wir zwei Ansätze:

• Naiver Ansatz: Erstellen Sie zwei verschachtelte Schleifen, um zu sehen, welche Elemente bereits vorhanden sind, und um zu verhindern, dass sie zur Ergebnisstapelrückgabe hinzugefügt werden.
• HashSet-Ansatz: Verwenden Sie ein Set, um eindeutige Elemente zu speichern, und nutzen Sie dessen O(1)-Komplexität, um zu überprüfen, ob ein Element vorhanden ist oder nicht.

Zufällige Stapel generieren und klonen

Unten ist dargestellt, wie das Java-Programm zunächst einen zufälligen Stapel erstellt und dann ein Duplikat davon zur weiteren Verwendung erstellt −

private static Stack initData(Long size) {
    Stack stack = new Stack  ();
    Random random = new Random();
    int bound = (int) Math.ceil(size * 0.75);
    for (int i = 0; i  manualCloneStack(Stack  stack) {
    Stack  newStack = new Stack  ();
    for (Integer item: stack) {
        newStack.push(item);
    }
    return newStack;
}

initData hilft beim Erstellen eines Stapels mit einer bestimmten Größe und zufälligen Elementen im Bereich von 1 bis 100.

manualCloneStack hilft bei der Datengenerierung durch das Kopieren von Daten aus einem anderen Stapel und verwendet sie für den Leistungsvergleich zwischen den beiden Ideen.

Entfernen Sie Duplikate aus einem bestimmten Stapel mit einem naiven Ansatz

Im Folgenden finden Sie die Schritte zum Entfernen von Duplikaten aus einem bestimmten Stapel mithilfe des naiven Ansatzes:

• Starten Sie den Timer.
• Erstellen Sie einen leeren Stapel, um eindeutige Elemente zu speichern.
• Iterieren Sie mit der While-Schleife und fahren Sie fort, bis der ursprüngliche Stapel leer ist. Öffnen Sie das oberste Element.
• Suchen Sie mit resultStack.contains(element) nach Duplikaten, um zu sehen, ob sich das Element bereits im Ergebnisstapel befindet.
• Wenn sich das Element nicht im Ergebnisstapel befindet, fügen Sie es dem Ergebnisstapel hinzu.
• Notieren Sie die Endzeit und berechnen Sie die insgesamt aufgewendete Zeit.
• Ergebnis zurückgeben

Beispiel

Unten finden Sie das Java-Programm zum Entfernen von Duplikaten aus einem bestimmten Stapel mithilfe des naiven Ansatzes −

public static Stack idea1(Stack stack) {
  long start = System.nanoTime();
  Stack resultStack = new Stack  ();

  while (!stack.isEmpty()) {
    int element = stack.pop();
    if (!resultStack.contains(element)) {
      resultStack.add(element);
    }
  }
  System.out.println("Time spent for idea1 is %d nanosecond".formatted(System.nanoTime() - start));
  return resultStack;
}

Für den naiven Ansatz verwenden wir

while (!stack.isEmpty())

resultStack.contains(element)

Duplikate aus einem bestimmten Stapel mit optimiertem Ansatz (HashSet) entfernen

Im Folgenden finden Sie die Schritte zum Entfernen von Duplikaten aus einem bestimmten Stapel mithilfe eines optimierten Ansatzes:

• Timer starten
• Erstellen Sie einen Satz, um gesehene Elemente zu verfolgen (für O(1)-Komplexitätsprüfungen).
• Erstellen Sie einen temporären Stapel zum Speichern eindeutiger Elemente.
• Iterieren Sie mit der while-Schleife und fahren Sie fort, bis der Stapel leer ist.
• Entfernen Sie das oberste Element vom Stapel.
• Um die Duplikate zu überprüfen, verwenden wir seen.contains(element), um zu prüfen, ob das Element bereits im Set vorhanden ist.
• Wenn sich das Element nicht im Satz befindet, fügen Sie es sowohl dem sichtbaren als auch dem temporären Stapel hinzu.
• Notieren Sie die Endzeit und berechnen Sie die insgesamt aufgewendete Zeit.
• Das Ergebnis zurückgeben

Beispiel

Unten finden Sie das Java-Programm zum Entfernen von Duplikaten aus einem bestimmten Stapel mithilfe von HashSet −

public static Stack idea2(Stack stack) {
    long start = System.nanoTime();
    Set seen = new HashSet();
    Stack tempStack = new Stack();

    while (!stack.isEmpty()) {
        int element = stack.pop();
        if (!seen.contains(element)) {
            seen.add(element);
            tempStack.push(element);
        }
    }
    System.out.println("Time spent for idea2 is %d nanosecond".formatted(System.nanoTime() - start));
    return tempStack;
}

Für einen optimierten Ansatz verwenden wir

Set seen

Beide Ansätze zusammen nutzen

Im Folgenden finden Sie die Schritte zum Entfernen von Duplikaten aus einem bestimmten Stapel mit beiden oben genannten Ansätzen:

• Daten initialisieren. Wir verwenden die Methode initData(Long size), um einen Stapel mit zufälligen Ganzzahlen zu erstellen.
  
• Klonen Sie den Stapel, den wir mit der Methode cloneStack(Stack stack) verwenden, um eine exakte Kopie des ursprünglichen Stapels zu erstellen.
• Generieren Sie den ersten Stapel mit initData.
• Klonen Sie diesen Stapel mit cloneStack.
• Wenden Sie den naiven Ansatz an, um Duplikate aus dem Originalstapel zu entfernen.
• Wenden Sie den optimierten Ansatz an, um Duplikate aus dem geklonten Stapel zu entfernen.
• Zeigen Sie die für jede Methode benötigte Zeit und die einzigartigen Elemente an, die durch beide Ansätze erzeugt werden

Beispiel

Unten finden Sie das Java-Programm, das doppelte Elemente aus einem Stapel entfernt, indem es beide oben genannten Ansätze verwendet –

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

public class DuplicateStackElements {
    private static Stack initData(Long size) {
        Stack stack = new Stack();
        Random random = new Random();
        int bound = (int) Math.ceil(size * 0.75);
        for (int i = 0; i  cloneStack(Stack stack) {
        Stack newStack = new Stack();
        newStack.addAll(stack);
        return newStack;
    }
    public static Stack idea1(Stack stack) {
        long start = System.nanoTime();
        Stack resultStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!resultStack.contains(element)) {
                resultStack.add(element);
            }
        }
        System.out.printf("Time spent for idea1 is %d nanoseconds%n", System.nanoTime() - start);
        return resultStack;
    }
    public static Stack idea2(Stack stack) {
        long start = System.nanoTime();
        Set seen = new HashSet();
        Stack tempStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!seen.contains(element)) {
                seen.add(element);
                tempStack.push(element);
            }
        }
        System.out.printf("Time spent for idea2 is %d nanoseconds%n", System.nanoTime() - start);
        return tempStack;
    }
    public static void main(String[] args) {
        Stack data1 = initData(10L);
        Stack data2 = cloneStack(data1);
        System.out.println("Unique elements using idea1: "   idea1(data1));
        System.out.println("Unique elements using idea2: "   idea2(data2));
    }
}

Ausgabe

Vergleich

* Die Maßeinheit ist Nanosekunde.

public static void main(String[] args) {
    Stack data1 = initData();
    Stack data2 = manualCloneStack(data1);
    idea1(data1);
    idea2(data2);
}

Wie beobachtet, ist die Laufzeit für Idee 2 kürzer als für Idee 1, da die Komplexität von Idee 1 O(n²) beträgt, während die Komplexität von Idee 2 O(n) beträgt. Wenn also die Anzahl der Stapel zunimmt, erhöht sich entsprechend auch der Zeitaufwand für Berechnungen.