Habe diese Frage auf Careercup.com gesehen:

Gegebene Höhen von n Personen, die in einer Linie stehen, und eine Liste von Zahlen für jede Person (p), die die Anzahl der Personen angibt, die größer als p sind und vor p stehen. Zum Beispiel,

Höhen: 5 3 2 6 1 4

InFronts: 0 1 2 0 3 2

Bedeutet, dass die tatsächliche tatsächliche Reihenfolge wie folgt lautet: 5 3 2 1 6 4

Die Frage ruft die beiden Listen mit Höhen und InFronts ab und sollte die Reihenfolge in einer Schlange generieren.

Meine Lösung:

Es könnte gelöst werden, indem die Liste zuerst in absteigender Reihenfolge sortiert wird. Offensichtlich müssen wir zum Sortieren ein Objekt Person definieren (mit zwei Attributen Höhe und InFront) und dann Personen nach ihrer Größe sortieren. Dann würde ich zwei Stapel verwenden, einen Hauptstapel und einen temporären Stapel, um die Reihenfolge aufzubauen.

Legen Sie es ausgehend vom höchsten in den Hauptstapel. Wenn die nächste Person einen InFront-Wert größer als die Person oben auf dem Stapel hatte, bedeutet dies, dass die neue Person vor der Person oben hinzugefügt werden sollte. Daher müssen wir Personen aus dem Hauptstapel entfernen, die neue Person einfügen und dann die Personen zurückgeben, die im ersten Schritt herausgekommen sind. Ich würde einen temporären Stapel verwenden, um die Reihenfolge der herausgesprungenen Personen aufrechtzuerhalten. Aber wie viele sollten herausspringen? Da die Liste sortiert ist, müssen wir genau die Anzahl der Personen vor die neue Person stellen, d. H. Die entsprechende InFront.

Ich denke diese Lösung funktioniert. Aber die schlechteste Reihenfolge wäre O (n ^ 2) - wenn eine Person eingerichtet werden soll, müssen alle vorherigen ausgelesen werden.

Gibt es noch andere Lösungen? möglicherweise in O (n)?