Ich habe eine Aufgabe, einen Algorithmus zu erstellen, um Duplikate in einem Array zu finden, das Zahlenwerte enthält. aber es hat nicht gesagt, welche Art von Zahlen, Ganzzahlen oder schwimmt. Ich habe folgenden Pseudocode geschrieben:
%Vor%habe ich einen effizienten Algorithmus erstellt? Ich denke, es gibt ein Problem in meinem Algorithmus, es gibt doppelte Zahlen mehrere Male zurück. Zum Beispiel wenn Array zwei in zwei für zwei Indizes enthält, werde ich ... 2, 2, ... in der Ausgabe haben. Wie kann ich es ändern, um jedes Duplikat nur einmal zurückzugeben? Ich denke, es ist ein guter Algorithmus für Ganzzahlen, aber funktioniert es auch gut für Gleitkommazahlen?
Möchten Sie Dubletten in Java finden?
Sie können ein HashSet verwenden.
%Vor%Der Rückgabewert von add () ist definiert als:
true, wenn der Satz nicht bereits vorhanden war enthält das angegebene Element.
BEARBEITEN: Ich weiß, HashSet ist für Einsätze optimiert und enthält Operationen. Aber ich bin mir nicht sicher, ob es schnell genug für deine Bedenken ist.
EDIT2: Ich habe gesehen, dass du kürzlich das Hausaufgaben-Tag hinzugefügt hast. Ich würde nicht meine Antwort bevorzugen, wenn es Hausaufgaben, weil es für eine Allgorithm-Lektion zu "high-level" sein kann
Ihre Antwort scheint ziemlich gut zu sein. Die erste Sortierung und die Überprüfung der Nachbarwerte ergibt O(n log(n)) complexity, was sehr effizient ist.
Merge sort ist O(n log(n)) , während benachbarte Werte einfach O(n) überprüft werden.
Eine Sache (wie in einem der Kommentare erwähnt) ist, dass Sie einen Stack-Überlauf (lol) mit Ihrem Pseudocode bekommen. Die innere Schleife sollte (in Java) lauten:
%Vor%Wenn Sie tatsächlich auch anzeigen möchten, welche Zahlen (und / oder Indizes) die Duplikate sind, müssen Sie sie in einer separaten Liste speichern.
Ich bin nicht sicher, in welcher Sprache Sie den Algorithmus schreiben müssen, aber es gibt einige wirklich gute C ++ - Lösungen als Reaktion auf meine Frage hier. Sollte dir von Nutzen sein.
Ihr Algorithmus enthält einen Pufferüberlauf. i beginnt mit 0, also nehme ich an, dass die Indizes in das Array A nullbasiert sind, d.h. das erste Element ist A[0] , das letzte ist A[A.length-1] . Jetzt zählt i bis zu A.length-1 und ruft im Schleifenkörper A[i+1] auf, das für die letzte Iteration außerhalb des Arrays liegt. Oder, einfach ausgedrückt: Wenn Sie jedes Element mit dem nächsten Element vergleichen, können Sie nur Vergleiche der Länge 1 durchführen.
Wenn Sie nur einmal Duplikate melden möchten, würde ich eine bool-Variable firstDuplicate verwenden, die auf false gesetzt wird, wenn Sie ein Duplikat finden, und auf true, wenn sich die Zahl von der nächsten unterscheidet. Dann würden Sie nur das erste Duplikat melden, indem Sie nur die doppelten Zahlen melden, wenn firstDuplicate wahr ist.
Tags und Links algorithm