Ich bin auf diese Frage gestoßen : Implementiere eine Warteschlange, in der push_rear (), pop_front () und get_min () konstante Zeitoperationen sind.
Ich dachte anfangs daran, eine Min-Heap-Datenstruktur zu verwenden, die O (1) -Komplexität für ein get_min () aufweist. Aber push_rear () und pop_front () wären O (log (n)).
Weiß jemand, wie man eine solche Warteschlange mit O (1) push (), pop () und min () am besten implementiert?
Ich habe darüber gegoogelt und wollte auf diesen Thread von Algorithm Geeks hinweisen . Es scheint jedoch, dass keine der Lösungen für alle drei Methoden der konstanten Zeitregel folgt: push (), pop () und min ().
Vielen Dank für alle Vorschläge.
Antworten:
Sie können einen Stapel mit O (1) pop (), push () und get_min () implementieren: Speichern Sie einfach das aktuelle Minimum zusammen mit jedem Element. So wird zum Beispiel der Stapel
[4,2,5,1]
(1 oben)[(4,4), (2,2), (5,2), (1,1)]
.Dann können Sie zwei Stapel verwenden, um die Warteschlange zu implementieren . Schieben Sie zu einem Stapel, Pop von einem anderen; Wenn der zweite Stapel während des Pops leer ist, verschieben Sie alle Elemente vom ersten Stapel zum zweiten.
Beispiel für eine
pop
Anforderung, bei der alle Elemente vom ersten Stapel verschoben werden[(4,4), (2,2), (5,2), (1,1)]
, wäre der zweite Stapel[(1,1), (5,1), (2,1), (4,1)]
. und jetzt das oberste Element vom zweiten Stapel zurückgeben.Um das minimale Element der Warteschlange zu finden, schauen Sie sich die kleinsten zwei Elemente der einzelnen Min-Stapel an und nehmen Sie dann das Minimum dieser beiden Werte. (Natürlich gibt es hier eine zusätzliche Logik, falls einer der Stapel leer ist, aber das ist nicht zu schwer zu umgehen).
Es wird O (1)
get_min()
undpush()
O (1) amortisiert habenpop()
.quelle
Okay - ich glaube, ich habe eine Antwort, die Ihnen alle diese Operationen in amortisiertem O (1) gibt, was bedeutet, dass jede Operation bis zu O (n) dauern kann, aber jede Folge von n Operationen O (1) Zeit pro Operation benötigt .
Die Idee ist, Ihre Daten als kartesischen Baum zu speichern . Dies ist ein Binärbaum, der der Eigenschaft min-heap gehorcht (jeder Knoten ist nicht größer als seine untergeordneten Knoten) und so angeordnet ist, dass Sie bei einer fehlerhaften Durchquerung der Knoten die Knoten in der Reihenfolge zurückgeben, in der sie hinzugefügt wurden. Hier ist zum Beispiel ein kartesischer Baum für die Sequenz
2 1 4 3 5
:Es ist möglich, ein Element in O (1) amortisierter Zeit in einen kartesischen Baum einzufügen, indem das folgende Verfahren angewendet wird. Schauen Sie sich den rechten Rücken des Baumes an (den Weg von der Wurzel zum Blatt ganz rechts, der gebildet wird, indem Sie immer nach rechts gehen). Beginnen Sie am Knoten ganz rechts und scannen Sie auf diesem Pfad nach oben, bis Sie den ersten Knoten finden, der kleiner als der Knoten ist, den Sie einfügen.
Ändern Sie diesen Knoten so, dass sein rechtes Kind dieser neue Knoten ist, und machen Sie dann das frühere rechte Kind dieses Knotens zum linken Kind des Knotens, den Sie gerade hinzugefügt haben. Angenommen, wir möchten eine weitere Kopie von 2 in den obigen Baum einfügen. Wir gehen den rechten Rücken entlang an den 5 und 3 vorbei, halten aber unterhalb der 1 an, weil 1 <2. Dann ändern wir den Baum so, dass er so aussieht:
Beachten Sie, dass eine Inorder Traversal 2 1 4 3 5 2 ergibt. Dies ist die Reihenfolge, in der wir die Werte hinzugefügt haben.
Dies läuft in amortisiertem O (1) ab, da wir eine potenzielle Funktion erstellen können, die der Anzahl der Knoten im rechten Rücken des Baums entspricht. Die zum Einfügen eines Knotens erforderliche Echtzeit beträgt 1 plus der Anzahl der Knoten in der Wirbelsäule, die wir berücksichtigen (nennen Sie dies k). Sobald wir den Platz zum Einfügen des Knotens gefunden haben, verkleinert sich die Größe der Wirbelsäule um die Länge k - 1, da sich jeder der k Knoten, die wir besucht haben, nicht mehr auf der rechten Wirbelsäule befindet und der neue Knoten an seiner Stelle ist. Dies ergibt amortisierte Kosten von 1 + k + (1 - k) = 2 = O (1) für den amortisierten O (1) -Einsatz. Als eine andere Art, darüber nachzudenken, ist ein Knoten, der einmal von der rechten Wirbelsäule entfernt wurde, nie wieder Teil der rechten Wirbelsäule, und wir werden ihn nie wieder bewegen müssen. Da jeder der n Knoten höchstens einmal verschoben werden kann, bedeutet dies, dass n Einfügungen höchstens n Bewegungen ausführen können.
Um einen Warteschlangenschritt auszuführen, entfernen wir einfach den Knoten ganz links aus dem kartesischen Baum. Wenn dieser Knoten ein Blatt ist, sind wir fertig. Andernfalls kann der Knoten nur ein Kind haben (das richtige Kind), und so ersetzen wir den Knoten durch sein rechtes Kind. Vorausgesetzt, wir verfolgen, wo sich der Knoten ganz links befindet, benötigt dieser Schritt O (1) Zeit. Nachdem Sie den Knoten ganz links entfernt und durch sein rechtes untergeordnetes Element ersetzt haben, wissen wir möglicherweise nicht, wo sich der neue Knoten ganz links befindet. Um dies zu beheben, gehen wir einfach den linken Rücken des Baumes entlang, beginnend mit dem neuen Knoten, den wir gerade zum Kind ganz links verschoben haben. Ich behaupte, dass dies immer noch in O (1) amortisierter Zeit läuft. Um dies zu sehen, behaupte ich, dass ein Knoten während eines dieser Durchgänge höchstens einmal besucht wird, um den Knoten ganz links zu finden. Beachten Sie, dass nach dem Besuch eines Knotens auf diese Weise Die einzige Möglichkeit, die wir jemals wieder betrachten könnten, wäre, wenn sie von einem untergeordneten Element des Knotens ganz links auf den Knoten ganz links verschoben würde. Alle besuchten Knoten sind jedoch Eltern des Knotens ganz links, sodass dies nicht passieren kann. Folglich wird jeder Knoten während dieses Vorgangs höchstens einmal besucht, und der Pop wird in O (1) ausgeführt.
Wir können find-min in O (1) machen, weil der kartesische Baum uns freien Zugang zum kleinsten Element des Baumes gibt; Es ist die Wurzel des Baumes.
Um zu sehen, dass die Knoten in der Reihenfolge zurückkehren, in der sie eingefügt wurden, beachten Sie, dass ein kartesischer Baum seine Elemente immer so speichert, dass eine Inorder-Traversierung sie in sortierter Reihenfolge besucht. Da wir bei jedem Schritt immer den Knoten ganz links entfernen und dies das erste Element der Inorder Traversal ist, erhalten wir die Knoten immer in der Reihenfolge zurück, in der sie eingefügt wurden.
Kurz gesagt, wir erhalten O (1) amortisiertes Push and Pop und O (1) Worst-Case-Find-Min.
Wenn ich eine O (1) -Implementierung im schlimmsten Fall finden kann, werde ich sie definitiv veröffentlichen. Das war ein großes Problem; danke fürs posten!
quelle
Ok, hier ist eine Lösung.
Zuerst brauchen wir einige Dinge, die push_back (), push_front (), pop_back () und pop_front () in 0 (1) bereitstellen. Es ist einfach mit Array und 2 Iteratoren zu implementieren. Der erste Iterator zeigt nach vorne, der zweite nach hinten. Nennen wir solche Sachen deque.
Hier ist Pseudocode:
Erläuterung:
Beispiel: Lassen Sie uns Zahlen [12,5,10,7,11,19] und in unsere MyQueue übertragen
1) Drücken von 12
2) Drücken von 5
3) Drücken von 10
4) Drücken von 7
6) Drücken von 11
7) Drücken von 19
Rufen wir jetzt pop_front () auf
wir haben
Das Minimum ist 5
Rufen wir noch einmal pop_front () auf
Erläuterung: pop_front entfernt 5 aus D, aber auch das vordere Element von Min, da es dem vorderen Element von D (5) entspricht.
Und das Minimum ist 7. :)
quelle
Verwenden Sie eine Deque (A) zum Speichern der Elemente und eine andere Deque (B) zum Speichern der Minima.
Wenn x in die Warteschlange gestellt ist, drücken Sie es zurück auf A und setzen Sie das Zurücksetzen von B fort, bis die Rückseite von B kleiner als x ist, und drücken Sie dann x auf B zurück.
Wenn Sie A aus der Warteschlange entfernen, wird pop_front A als Rückgabewert verwendet. Wenn es gleich der Vorderseite von B ist, wird pop_front B ebenfalls verwendet.
Wenn Sie das Minimum von A erhalten, verwenden Sie die Vorderseite von B als Rückgabewert.
Dequeue und Getmin sind offensichtlich O (1). Berücksichtigen Sie für die Enqueue-Operation den push_back von n Elementen. Es gibt n Push_back zu A, n Push_back zu B und höchstens n Pop_back von B, da jedes Element entweder in B bleibt oder einmal aus B herausspringt. Insgesamt gibt es O (3n) -Operationen und daher betragen die fortgeführten Anschaffungskosten O. (1) auch für die Warteschlange.
Der Grund, warum dieser Algorithmus funktioniert, ist, dass wenn Sie x in A einreihen und Elemente in B größer als x sind, diese jetzt niemals minimal sind, da x länger in der Warteschlange A bleibt als alle Elemente in B (eine Warteschlange) ist FIFO). Daher müssen wir Elemente in B (von hinten) herausspringen lassen, die größer als x sind, bevor wir x in B verschieben.
quelle
Wenn es Ihnen nichts ausmacht, ein paar zusätzliche Daten zu speichern, sollte es trivial sein, den Mindestwert zu speichern. Push and Pop kann den Wert aktualisieren, wenn das neue oder entfernte Element das Minimum ist, und die Rückgabe des Minimalwerts ist so einfach wie das Abrufen des Werts der Variablen.
Dies setzt voraus, dass get_min () die Daten nicht ändert; Wenn Sie lieber etwas wie pop_min () haben möchten (dh das minimale Element entfernen möchten), können Sie einfach einen Zeiger auf das tatsächliche Element und das vorhergehende Element (falls vorhanden) speichern und diese entsprechend mit push_rear () und pop_front () aktualisieren. auch.
Nach Kommentaren bearbeiten:
Offensichtlich führt dies zu O (n) Push and Pop für den Fall, dass sich das Minimum bei diesen Operationen ändert und somit die Anforderungen nicht strikt erfüllt.
quelle
Lösungen für diese Frage, einschließlich Code, finden Sie hier: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32
quelle
Sie können tatsächlich eine LinkedList verwenden, um die Warteschlange zu verwalten.
Jedes Element in LinkedList ist vom Typ
Sie können zwei Zeiger haben. Einer zeigt auf den Anfang und der andere auf das Ende.
Wenn Sie dem Anfang der Warteschlange ein Element hinzufügen. Untersuchen Sie den Startzeiger und den einzufügenden Knoten. Wenn der Knoten zum Einfügen von currentmin kleiner als der Start ist, ist der Knoten zum Einfügen von currentmin das Minimum. Andernfalls aktualisieren Sie currentmin mit start currentmin.
Wiederholen Sie das gleiche für Enque.
quelle
quelle
Diese Lösung enthält 2 Warteschlangen:
1. main_q - speichert die Eingabenummern.
2. min_q - speichert die min-Zahlen nach bestimmten Regeln, die wir beschrieben haben (erscheinen in den Funktionen MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ()).
Hier ist der Code in Python. Die Warteschlange wird mithilfe einer Liste implementiert.
Die Hauptidee liegt in den Funktionen MainQ.enqueue (x), MainQ.dequeue (), MainQ.get_min ().
Eine wichtige Annahme ist, dass das Leeren einer Warteschlange o (0) dauert.
Am Ende wird ein Test bereitgestellt.
Die Ausgabe des obigen Tests ist:
quelle
Java-Implementierung
quelle
JavaScript-Implementierung
( Dank an adamax 'Lösung für die Idee; ich habe eine Implementierung lose darauf aufgebaut. Springen Sie nach unten, um vollständig kommentierten Code zu sehen, oder lesen Sie die folgenden allgemeinen Schritte durch. Beachten Sie, dass dies den Maximalwert in O (1) konstanter Zeit anstelle von findet der Mindestwert - leicht zu ändern):
Einfügen: O (1) Worst Case
Streichung: O (1) abgeschrieben
Finden des Maximalwerts: O (1) Worst Case
Code
class MaxQueue { constructor(...data) { // create a dequeue Stack from which we'll pop this.dqStack = new Stack(); // create an enqueue Stack to which we'll push this.eqStack = new Stack(); // if enqueueing data at construction, iterate through data and enqueue each if (data.length) for (const datum of data) this.enqueue(datum); } enqueue(data) { // O(1) constant insertion time // if the MaxQueue is empty, if (!this.peek()) { // push data to the dequeue Stack and indicate it's the max; this.dqStack.push([data, data]); // e.g., enqueue(8) ==> [data: 8, max: 8] } else { // otherwise, the MaxQueue is not empty; push data to enqueue Stack this.eqStack.push(data); // save a reference to the tuple that's next in line to be dequeued const next = this.dqStack.peek(); // if the enqueueing data is > the max in that tuple, update it if (data > next[1]) next[1] = data; } } moveAllFromEqToDq() { // O(1) amortized as each value will move at most once // start max at -Infinity for comparison with the first value let max = -Infinity; // until enqueue Stack is empty, while (this.eqStack.peek()) { // pop from enqueue Stack and save its data const data = this.eqStack.pop(); // if data is > max, set max to data if (data > max) max = data; // push to dequeue Stack and indicate the current max; e.g., [data: 7: max: 8] this.dqStack.push([data, max]); } } dequeue() { // O(1) amortized deletion due to calling moveAllFromEqToDq from time-to-time // if the MaxQueue is empty, return undefined if (!this.peek()) return; // pop from the dequeue Stack and save it's data const [data] = this.dqStack.pop(); // if there's no data left in dequeue Stack, move all data from enqueue Stack if (!this.dqStack.peek()) this.moveAllFromEqToDq(); // return the data return data; } peek() { // O(1) constant peek time // if the MaxQueue is empty, return undefined if (!this.dqStack.peek()) return; // peek at dequeue Stack and return its data return this.dqStack.peek()[0]; } getMax() { // O(1) constant time to find maximum value // if the MaxQueue is empty, return undefined if (!this.peek()) return; // peek at dequeue Stack and return the current max return this.dqStack.peek()[1]; } }
quelle
Wir wissen, dass Push und Pop konstante Zeitoperationen sind [O (1) um genau zu sein].
Wenn wir jedoch an get_min () denken [dh die aktuelle Mindestanzahl in der Warteschlange ermitteln], fällt uns im Allgemeinen als Erstes ein, dass die gesamte Warteschlange jedes Mal durchsucht wird, wenn die Anforderung nach dem Mindestelement erfolgt. Dies wird jedoch niemals den Betrieb mit konstanter Zeit ergeben, was das Hauptziel des Problems ist.
Dies wird in der Regel sehr häufig in den Interviews gefragt, daher müssen Sie den Trick kennen
Dazu müssen wir zwei weitere Warteschlangen verwenden, die den Überblick über das minimale Element behalten, und wir müssen diese beiden Warteschlangen weiter ändern, während wir Push- und Pop-Operationen in der Warteschlange ausführen, sodass das minimale Element in O (1) -Zeit erhalten wird .
Hier ist der selbstbeschreibende Pseudocode, der auf dem oben erwähnten Ansatz basiert.
quelle