Ist dieser Ansatz zum Überprüfen von Duplikaten in einem Array relativ effizient? Warum oder warum nicht?

Question

Ich wollte nur überprüfen, ob in meinem Array Dubletten enthalten sind. Ich auf Google gesucht und einige Ansätze sehen:

• Doppel for-Schleife Schleifen obwohl das Array und vergleicht jedes Element
• ein Wörterbuch erstellen, die die Anzahl von Vorkommen jedes Element speichert

Aber diese Methoden erfordern viele Schleifen und ich bin irgendwie faul, eine große Menge an Code nur für diese Funktionalität zu schreiben. xD. So

Ich dachte, dieser kreative Art und Weise:

let containsDuplicates = Set(array).count != array.count 

Dieses Verfahren ist jedoch schneller oder langsamer als die anderen beiden? Ich bin mir nicht sicher, weil es scheint, ein Set zu erstellen, das ich denke, muss durch das Array durchlaufen. Und ich weiß nicht, ob der Zugriff auf die count auch das gesamte Array durchläuft.

Wenn ich nur höchstens 50 Elemente im Array habe, ist das überhaupt von Bedeutung?

Answer 1

Das ist so ziemlich der beste Weg. Dictionary-Speicher ist konstante Zeit, und jedes Element muss nur einmal gespeichert werden, so ist es eine O(n) Lösung, die O(n^2) für die doppelte for-Schleife-Ansatz. Die Raumeffizienz ist geringer, aber das ist heutzutage normalerweise kein Problem.

Wenn Sie dies oft tun, würde ich vorschlagen, eine Art von hybriden Datenstruktur zu verwenden, so dass Sie diese Set s nicht von Grund auf neu generieren.

Answer 2

Mein erster Gedanke war, ein Set zu erstellen und zu sehen, ob die Anzahl der Elemente anders als das Array ist, genau wie Sie. Apple wird diese Konvertierung wahrscheinlich ziemlich gut optimiert haben, und auf diese Weise wird der Code kompakt und leicht verständlich.

Sie erwähnen nicht, wozu das Array gehört und wie es verwendet wird, aber könnten Sie einfach ein Set anstelle des Arrays verwenden, so dass Duplikate gar nicht erst hinzugefügt werden? Oder wenn Sie den Überblick behalten müssen, wie viele, aber trotzdem die eindeutigen Werte kennen müssen, erstellen Sie eine neue Klasse, die ein Wörterbuch für den Speicher verwendet. Der Schlüssel ist, was Sie im Array speichern, aber wäre einzigartig und der Wert wäre die Anzahl.