Ein Element, das sich in zwei Arrays unterscheidet. Wie finde ich es effizient?

22

Ich bereite mich auf ein Coding-Interview vor und kann nicht wirklich herausfinden, wie dieses Problem am effizientesten gelöst werden kann.

Angenommen, wir haben zwei Arrays, die aus nicht sortierten Zahlen bestehen. Array 2 enthält eine Nummer, die Array 1 nicht enthält. Beide Arrays haben zufällig angeordnete Zahlen, nicht unbedingt in derselben Reihenfolge oder bei denselben Indizes. Beispielsweise:

Array 1 [78, 11, 143, 84, 77, 1, 26, 35 ... n]

Array 2 [11,84, 35, 25, 77, 78, 26, 143 ... 21 ... n + 1]

Was ist der schnellste Algorithmus, um die abweichende Zahl zu finden? Was ist die Laufzeit? In diesem Beispiel ist die gesuchte Nummer 21.

Meine Idee war, Array 1 zu durchlaufen und diesen Wert aus Array 2 zu löschen. Iterieren Sie, bis Sie fertig sind. Dies sollte ungefähr Laufzeit sein, richtig?O(nlogn)

Konstantino Sparakis
quelle
@Jandvorak Vielen Dank für die Antworten. Ich war spät auf und schlief zufällig ein, nachdem ich dies gepostet hatte. Das Array ist unsortiert und alle Elemente werden in beiden Arrays in zufälligen Indizes angezeigt.
Konstantino Sparakis
@ KonstantinoSparakis: Diese Klarstellung macht die Antworten ungültig, die davon ausgehen, dass beide Arrays die Elemente an den gleichen Positionen enthalten.
Mario Cervera
Cross Posting ist verpönt über softwareengineering.stackexchange.com/users/256931/…
paparazzo
@Paparazzi Ich suchte einfach nach einer Lösung, die ich in der Meta-Software-Technik gelesen hatte, und wollte eine Lösung finden, wusste aber zu der Zeit nichts über das CS-Forum. Ich habe die Mods benachrichtigt, um es aufzuräumen.
Konstantino Sparakis
@Paparazzi Gibt es einen Meta-Post, der das unterstützt? Ich persönlich sehe keine Möglichkeit, diese Politik gut umzusetzen.
Djechlin

Antworten:

30

Ich sehe vier Möglichkeiten, um dieses Problem mit unterschiedlichen Laufzeiten zu lösen:

  • O(n2) -Lösung: Dies ist die von Ihnen vorgeschlagene Lösung. Da die Arrays nicht sortiert sind, dauert das Löschen linear. Sie führen Löschungen durch; Daher benötigt dieser Algorithmus quadratische Zeit.n

  • Lösung: Sortieren Sie die Arrays im Voraus. Führen Sie dann eine lineare Suche durch, um das bestimmte Element zu identifizieren. Bei dieser Lösung wird die Laufzeit vom Sortiervorgang dominiert, daher der O ( nO(nlogn) Obergrenze.O(nlogn)

Wenn Sie eine Lösung für ein Problem finden, sollten Sie sich immer fragen: Kann ich es besser machen? In diesem Fall können Sie Datenstrukturen geschickt nutzen. Beachten Sie, dass Sie lediglich ein Array durchlaufen und im anderen Array wiederholt nachschlagen müssen. Mit welcher Datenstruktur können Sie in (erwarteter) konstanter Zeit nachschlagen? Sie haben richtig geraten: ein Hash-Tisch .

  • Lösung (erwartet): Iteriere das erste Array und speichere die Elemente in einer Hash-Tabelle; Führen Sie dann im zweiten Array einen linearen Scan durch, indem Sie jedes Element in der Hash-Tabelle nachschlagen. Gibt das Element zurück, das nicht in der Hash-Tabelle gefunden wurde. Diese Lösung mit linearer Zeit funktioniert für alle Arten von Elementen, die Sie an eine Hash-Funktion übergeben können (z. B. würde sie für Strings-Arrays ähnlich funktionieren).O(n)

Wenn Sie obere Garantien wünschen und die Arrays streng aus ganzen Zahlen bestehen, ist die beste Lösung wahrscheinlich die von Tobi Alafin vorgeschlagene (auch wenn diese Lösung nicht den Index des Elements liefert, das sich im zweiten Array unterscheidet). :

  • Lösung (garantiert): Summiere die Elemente des ersten Arrays. Fassen Sie dann die Elemente des zweiten Arrays zusammen. Führen Sie abschließend die Subtraktion durch. Beachten Sie, dass diese Lösung dank desbitweisen XOR-Operatorsauf jeden Datentyp verallgemeinert werden kann, dessen Werte als Bitfolgen fester Länge dargestelltwerden können. Dies wird inderAntwort vonIlmari Karonenausführlich erklärt. O(n)

Schließlich wäre eine andere Möglichkeit (unter der gleichen Annahme von Ganzzahl-Arrays) die Verwendung eines linearen Zeit-Sortieralgorithmus wie Zählsortierung. Dies würde die Laufzeit der sortierungsbasierten Lösung von bis O ( n ) .O(nlogn)O(n)

Mario Cervera
quelle
4
Die Summierung ist jedoch nicht linear, wenn die Zahlen groß genug werden.
Sarge Borsch
9
Eine nette Sache am Summierungsalgorithmus ist, dass er mit jeder abelschen Gruppe funktioniert, nicht nur mit ganzen Zahlen (vor allem uint64; cc @sarge).
John Dvorak
6
@Abdul die Sache ist, wenn Ihre ganzen Zahlen sehr groß sind, können Sie nicht mehr so ​​tun, als ob sie zum Hinzufügen brauchen . Ich glaube , die Komplexität wächst auf O ( n ln n ) , wenn Sie für dieses Konto. Die Verwendung von XOR anstelle einer gewöhnlichen Addition löst dieses Problem, während die Eingabe dennoch eine willkürlich große Anzahl zulässt. O(n)O(nlnn)
John Dvorak
2
@ JanDvorak Nein, das tut es nicht. Sie gehen davon aus, dass die für die abelsche Gruppe definierte Operation eine konstante Zeit benötigt. Das kann man nicht einfach so annehmen.
UTF-8
2
@ UTF-8 Das nehme ich nicht an. Dies geschieht jedoch in endlichen Gruppen (uint64), und die digitale In-Place-Addition (Addition in ) ist linear in der Größe des ex -Place-Operanden. Die Berechnung der Summe in solchen Gruppen ist also in der Gesamtgröße der Operanden linear zeitlich. Znd
John Dvorak
16

Das Differenz von Summen Lösung vorgeschlagen Tobi und Mario kann in der Tat zu jedem anderen Datentyp verallgemeinert werden , für die wir eine (konstante Zeit) Binäroperation definieren , der:Θ(n)

  • insgesamt , so dass für alle Werte und b , a b definiert und von der gleichen Art (oder zumindest von einigen geeigneten Supertypen davon, für die der Betreiber definiert ist nach wie vor);abab
  • assoziativ , so dass ;a(bc)=(ab)c
  • kommutativ , so dass ; undab=ba
  • cancellative , so dass es existiert ein inverser Operator dass erfüllt ( a b ) b = a . Technisch gesehen muss diese inverse Operation nicht unbedingt eine konstante Zeit sein, solange das "Subtrahieren" von zwei Summen von jeweils n Elementen nicht mehr als O ( n ) Zeit in Anspruch nimmt .(ab)b=anO(n)

(Wenn der Typ nur eine begrenzte Anzahl unterschiedlicher Werte annehmen kann, reichen diese Eigenschaften aus, um ihn in eine abelsche Gruppe zu verwandeln . Selbst wenn dies nicht der Fall ist, handelt es sich zumindest um eine kommutative abbrechende Halbgruppe .)

Mit einer solchen Operation können wir die "Summe" eines Arrays a = ( a 1 , a 2 , , a n ) als ( ⊕ definierena=(a1,a2,,an) Wenn ein anderes Array b = ( b 1 , b 2 , ... , b n , b n + 1 ) alle Elemente von a plus ein zusätzliches Element x enthält , haben wir somit ( ⊕)

(a)=a1a2an.
b=(b1,b2,,bn,bn+1)ax , und so können wir dieses zusätzliche Element finden, indem wir berechnen: x = ( (b)=(a)x
x=(b)(a).

Wenn beispielsweise die Werte in den Arrays ganze Zahlen sind, dann ganzzahlige Addition (oder modulare Addition für finite Länge ganzen Zahlen Typen) kann als Operator verwendet werden , mit Subtraktion als die inverse Operation . Alternativ kann für jeden Datentyp , deren Werte als fester Länge Bit - Strings dargestellt werden, können wir verwenden bitweise XOR als beide und .

Im Allgemeinen können wir die bitweise XOR-Methode sogar auf Zeichenfolgen variabler Länge anwenden, indem wir sie auf die erforderliche Länge auffüllen, sofern wir die Möglichkeit haben, die Auffüllung am Ende reversibel zu entfernen.

In einigen Fällen ist dies trivial. Beispielsweise codieren nullterminierte Byte-Strings im C-Stil implizit ihre eigene Länge, sodass die Anwendung dieser Methode für sie trivial ist: Wenn Sie zwei Strings per XOR verknüpfen, füllen Sie den kürzeren String mit null Bytes auf, damit die Länge übereinstimmt, und schneiden Sie alle zusätzlichen nachgestellten Nullen ab das Endergebnis. Beachten Sie, dass die XOR-Summen-Zwischenzeichenfolgen jedoch Null-Bytes enthalten können , sodass Sie deren Länge explizit speichern müssen (Sie benötigen jedoch höchstens ein oder zwei davon).

1001232Bei einer Länge von Bytes können wir die Länge jeder Zeichenfolge als 32-Bit-Ganzzahl codieren und der Zeichenfolge voranstellen. Oder wir könnten sogar beliebige Zeichenfolgenlängen mit einem Präfixcode codieren und diese den Zeichenfolgen voranstellen. Es gibt auch andere mögliche Codierungen.

Θ(n)

Der einzige potenziell schwierige Teil besteht darin, dass wir eine eindeutige kanonische Bitstring-Darstellung für jeden Wert auswählen müssen, damit die Löschung funktioniert. Dies kann schwierig (möglicherweise sogar rechnerisch unentscheidbar) sein, wenn die Eingabewerte in den beiden Arrays angegeben werden in verschiedenen äquivalenten Darstellungen. Dies ist jedoch keine spezifische Schwäche dieser Methode; Jede andere Methode zur Lösung dieses Problems kann ebenfalls zum Scheitern verurteilt werden, wenn die Eingabe Werte enthalten darf, deren Äquivalenz nicht entschieden werden kann.

Ilmari Karonen
quelle
Wow, sehr interessante Einstellung dazu. Vielen Dank @IlmariKaronen
Konstantino Sparakis
14

Ich würde dies als Kommentar zu Tobis Antwort posten, aber ich habe noch keinen Ruf.

Alternativ zur Berechnung der Summe jeder Liste (insbesondere, wenn es sich um große Listen handelt oder wenn sie sehr große Zahlen enthalten, die Ihren Datentyp bei der Summierung möglicherweise überschreiten) können Sie stattdessen xor verwenden.

Berechnen Sie einfach die xoder-Summe (dh x [0] ^ x [1] ^ x [2] ... x [n]) jeder Liste und xoder diese beiden Werte. Dies gibt Ihnen den Wert des fremden Elements (aber nicht den Index).

Dies ist immer noch O (n) und vermeidet Probleme mit Überlauf.

reffu
quelle
3
Ich würde auch XOR verwenden, weil es ein bisschen ordentlicher erscheint, aber um fair zu sein, ist Überlauf kein wirkliches Problem, solange die Sprache, in der Sie dies implementieren, Überlauf durch Zeilenumbruch unterstützt.
Martin Ender
14

Element = Summe (Array2) - Summe (Array1)

Ich bezweifle aufrichtig, dass dies der optimalste Algorithmus ist. Aber es ist ein anderer Weg, das Problem zu lösen, und es ist der einfachste Weg, es zu lösen. Ich hoffe es hilft.

Wenn die Anzahl der hinzugefügten Elemente mehr als eins beträgt, funktioniert dies nicht.

Meine Antwort hat die gleiche Laufzeitkomplexität für den besten, schlechtesten und durchschnittlichen Fall.

BEARBEITEN
Nach einigem Nachdenken denke ich, dass meine Antwort Ihre Lösung ist.

nn-11=n-12=n+1-1=n

2n-12-1=1

2n-1+1=2n

Θ(n)

BEARBEITEN:
Aufgrund einiger Probleme mit Datentypen ist eine von reffu vorgeschlagene XOR-Summe geeigneter.

Tobi Alafin
quelle
Beachten Sie, dass diese Methode möglicherweise keine genaue Antwort liefert, wenn es sich bei Ihren Werten um Gleitkommazahlen handelt, da das Summieren der Zahlen zu Rundungsfehlern führen kann. Dies funktioniert jedoch für ganzzahlige Werte, vorausgesetzt, dass entweder a) Ihr ganzzahliger Typ ein genau definiertes Umlaufverhalten beim Überlauf aufweist oder b) Sie die Summen in Variablen eines Typs speichern, der breit genug ist, dass sie nicht überlaufen können.
Ilmari Karonen
Rubys "BigNum" -Klasse kann wahrscheinlich damit umgehen.
Tobi Alafin
Es funktioniert absolut nicht, wenn Ihr Array beispielsweise Zeichenfolgen enthält oder so ziemlich alles, was nicht sinnvoll hinzugefügt werden kann.
gnasher729
Ja, wurde mir klar. Was ist mit 'XOR'? Funktioniert es bei Schwimmern?
Tobi Alafin
Ja und auch Zeiger und im Allgemeinen alles, was aus einer festen Anzahl von Bits besteht. Viele Sprachen unterstützen das nicht, aber das ist kein grundlegendes Problem. Modulare Addition / Subtraktion funktioniert in den gleichen Fällen.
Harold
1

Angenommen, Array 2 wurde durch Aufnehmen von Array 1 und Einfügen eines Elements an einer zufälligen Position erstellt, oder Array 1 wurde durch Aufnehmen von Array 2 und Löschen eines zufälligen Elements erstellt.

Wenn garantiert ist, dass alle Array-Elemente eindeutig sind, ist die Zeit O (ln n). Sie vergleichen die Elemente an Position n / 2. Wenn sie gleich sind, reicht das zusätzliche Element von n / 2 + 1 bis zum Ende des Arrays, andernfalls von 0 bis n / 2. Und so weiter.

Wenn die Unterscheidbarkeit der Array-Elemente nicht garantiert ist: Sie könnten n-mal die Nummer 1 in Array 1 und die Nummer 2 an einer beliebigen Stelle in Array 2 einfügen. In diesem Fall können Sie nicht wissen, wo sich die Nummer 2 befindet, ohne überhaupt nachzuschauen Array-Elemente. Daher O (n).

PS. Da sich die Anforderungen geändert haben, prüfen Sie in Ihrer Bibliothek, was verfügbar ist. Unter macOS / iOS erstellen Sie ein NSCountedSet, fügen alle Zahlen aus Array 2 hinzu, entfernen alle Zahlen aus Array 1, und es bleibt alles übrig, was sich in Array 2 befindet, jedoch nicht in Array 1, ohne sich auf die Behauptung zu verlassen, dass es ein zusätzliches gibt Artikel.

gnasher729
quelle
Diese Antwort war genau richtig, aber die Frage wurde mit einer neuen Anforderung bearbeitet, die Ihre Annahme ungültig macht.
Mario Cervera
Ihre neue Antwort scheint richtig zu sein. Was ist die zeitliche Komplexität?
Tobi Alafin
Nun, zuerst was ist die Zeit, die benötigt wird, um den Code zu schreiben. Es ist trivial. NSCountedSet verwendet Hashing, daher ist die Zeitkomplexität "normalerweise linear".
gnasher729
-1

var am kürzesten, am längsten;

Konvertieren Sie den kürzesten Wert in eine Karte für eine schnelle Referenzierung und die Schleife über den längsten Wert, bis der aktuelle Wert nicht mehr in der Karte enthalten ist.

So etwas in Javascript:

if (arr1.length> arr2.length) {Shortest = arr2; am längsten = arr1; } sonst {am kürzesten = arr1; am längsten = arr2; }

var map = Shortest.reduce (Funktion (obj, Wert) {obj [Wert] = true; return obj;}, {});

var difference = longest.find (function (value) {return !!! map [value];});

Craig Hardcastle
quelle
Codes ohne Erklärung zählen hier nicht als gute Antwort. Auch warum würdest du verwenden !!! ?
Evil
-1

O (N) Lösung in zeitlicher Komplexität O (1) in räumlicher Komplexität

Problemstellung: Angenommen, Array2 enthält alle Elemente von Array1 sowie ein weiteres Element, das in Array1 nicht vorhanden ist.

Die Lösung lautet: Wir verwenden xor, um das Element zu finden, das in Array1 nicht vorhanden ist. Die Schritte lauten also: 1. Beginnen Sie mit Array1 und führen Sie xor aller Elemente aus und speichern Sie sie in einer Variablen. 2. Nehmen Sie das Array2 und führen Sie das xor aller Elemente mit der Variablen aus, in der das xor von Array1 gespeichert ist. 3. Nach dem Ausführen der Operation enthält unsere Variable das Element, das nur in Array2 vorhanden ist. Der obige Algorithmus funktioniert aufgrund der folgenden Eigenschaft von xor "a xor a = 0" "a xor 0 = a" Ich hoffe, dies löst Ihr Problem. Auch die oben vorgeschlagenen Lösungen sind in Ordnung

Dummer Fehler
quelle