Ich wurde heute in einem Interview nach einer algorithmischen Frage gefragt und würde mich freuen, SO-Mitglieder dazu zu bringen. Die Frage war wie folgt:
Bei gleicher Größe von N-Arrays mit Ganzzahlen in aufsteigender Reihenfolge würden Sie die für alle N-Arrays gemeinsamen Zahlen auswählen.
Zuerst dachte ich daran, über Elemente zu iterieren, die vom ersten Array bis zum Rest der Arrays reichen. Aber das würde dann zu N power N Iterationen führen, wenn ich recht habe. Also habe ich mir eine Lösung ausgedacht, um die Anzahl zu einer Karte hinzuzufügen, indem ich das Element als Schlüssel und den Wert als Zähler behalte. Auf diese Weise glaube ich, dass die Zeitkomplexität nur N ist. Es folgt die Implementierung meines Ansatzes in Java.
%Vor%Ich habe das gerade für drei Arrays gemacht, um zu sehen, wie es funktioniert. Frage spricht über N Arrays, obwohl ich denke, das würde immer noch halten.
Meine Frage ist, gibt es einen besseren Ansatz, um dieses Problem mit der Zeit Komplexität im Auge zu behalten?
Behandle 3 Warteschlangen. Während die Werte unterschiedlich sind, ist "remove" (durch Inkrementieren des Array-Index) der kleinste. Wenn sie übereinstimmen, "entferne" (und zeichne) die Übereinstimmungen auf.
%Vor%Leicht verallgemeinerbar für N-Arrays, aber mit N large würden Sie die Vergleiche irgendwie optimieren wollen (NPEs "Heap").
Ich denke, dass dies mit einer einzigen parallelen Iteration über die N-Arrays und einem N-Element Min-Heap . Im Heap würden Sie das aktuelle Element von jedem der N Eingangsarrays behalten.
Die Idee ist, dass Sie bei jedem Schritt entlang des Arrays weitergehen, dessen Element sich an der Spitze des Heaps befindet (d. h. ist der kleinste).
Sie müssen erkennen können, wenn der Heap vollständig aus identischen Werten besteht. Dies kann in konstanter Zeit erfolgen, solange Sie das größte Element verfolgen, das Sie dem Heap hinzugefügt haben.
Wenn jedes Array M Elemente enthält, wäre die Zeitkomplexität im schlimmsten Fall O(M*N*log(N)) und würde O(N) Speicher erfordern.
So habe ich gelernt, es in einer Klasse von Algorithmen zu machen. Nicht sicher, ob es "besser" ist, aber es benötigt weniger Speicher und weniger Overhead, da es direkt durch die Arrays iteriert, anstatt zuerst eine Karte zu erstellen.
%Vor% Dies kann in O(M * N) gelöst werden, wobei M die Länge von Arrays ist.
Lassen Sie uns sehen, was für N = 2 passiert, dies wäre ein Problem mit der sortierten Liste, bei dem eine klassische merge-ähnliche Lösung in O(l1 + l2) time läuft. (l1 = Länge des ersten Arrays, l2 = Länge des zweiten Arrays). (Erfahren Sie mehr über Merge Algorithms .)
Lassen Sie uns nun den Algorithmus N-mal in einer induktiven Angelegenheit wiederholen. (Zum i-ten Mal haben wir das i-te Array und das Kreuzungsergebnis des vorherigen Schritts). Dies würde zu einem allgemeinen Algorithmus O(M * N) führen.
Sie können auch beobachten, dass diese Obergrenze des schlimmsten Falls am besten erreichbar ist, da alle Zahlen für jeden gültigen Algorithmus berücksichtigt werden müssen. Es kann also kein deterministischer Algorithmus mit einer höheren Obergrenze gefunden werden.
Okay - vielleicht ein bisschen naiv hier, aber ich denke, der Hinweis ist, dass die Arrays in aufsteigender Reihenfolge sind. Mein Java ist rostig, aber hier ist etwas pseduocode. Ich habe es nicht getestet, also ist es wahrscheinlich nicht perfekt, aber es sollte ein schneller Weg sein, dies zu tun:
%Vor%Dies ist Optionsbasis 1 - Sie müssten die Optionsbase 0 neu codieren (wie Java und andere Sprachen)
Ich denke, ein anderer Ansatz besteht darin, Ähnliches zu tun, was wir in Mergesort tun: Durch alle Arrays gleichzeitig gehen und identische Zahlen erhalten. Dies würde den Vorteil ausnutzen, dass die Arrays in einer sortierten Reihenfolge sind und keinen zusätzlichen Raum außer dem Ausgangsarray verwenden würden. Wenn Sie nur die allgemeinen Zahlen drucken müssen, wird kein zusätzlicher Speicherplatz verwendet.
%Vor%Um dies allgemeiner zu machen, können Sie Arrays mit Arrays von Ints verwenden, damit Sie den Code hübscher gestalten können. Die Array-Indices müssen in einem Array gespeichert werden, andernfalls ist es schwierig, den Code "Inkrement des Index, der auf die niedrigste Nummer zeigt" zu codieren.
Ihre Lösung ist akzeptabel, verwendet jedoch NxM-Speicherplatz. Sie können es mit O (N) space (wobei N die Anzahl der Arrays ist) oder in O (1) space verwenden.
Lösung # 1 (Von Luigi Mendoza)
Unter der Annahme, dass viele kleine Arrays (M & lt; & lt; N) vorhanden sind, kann dies nützlich sein, was zu O (M * N * Log M) -Zeit und konstantem Raum (ohne die Ausgabeliste) führt.
Lösung # 2
Scannen Sie die Arrays in aufsteigender Reihenfolge, wobei Sie einen Min-Heap der Größe N beibehalten, der die zuletzt besuchten Werte (und Indizes) der Arrays enthält. Wenn der Heap N Kopien desselben Werts enthält, fügen Sie den Wert zur Ausgabesammlung hinzu. Andernfalls entfernen Sie den Mindestwert und fahren Sie mit der entsprechenden Liste fort.
Die Zeitkomplexität dieser Lösung ist O (M * N * Log N)