Sortieren einer Liste entsprechend Auftrag durch eine andere Liste definiert

Question

Wie kann ich irgendwie die Elemente der Liste A , so dass sie die Bestellung einer anderen (Obermenge) Liste B folgen? Annahme, dass keine Duplikate.

z. A enthalten könnte [8 2 5 1] und B könnte enthalten [5 6 9 8 7 4 1 2 3], so ich möchte sort A werden [5 8 1 2]

Ich habe Interesse an Möglichkeiten, dies zu tun, effizient und mit guter Laufzeitkomplexität.

Answer 1

Wenn B ist eine Obermenge von A , würde ich nur Dump A in eine Hash-Tabelle, Scan B und eine neue Liste erstellen, in dem ich jedes Element von B , die in der Hash-Tabelle enthalten ist. Uses O (a) zusätzliche Speicher und O (b) Laufzeit.

Answer 2

Hier sind einige Ideen:

(In der Zeit Komplexität gegeben, n ist die Größe von A und m ist die Größe von B . nicht vereinfacht die Zeit Komplexität.)

• Für jedes Element in B , führen Sie eine lineare Suche von A , um zu sehen, ob das Elemente in ihm vorhanden ist. Wenn ja, tauschen sie mit dem ersten Element in A , die noch nicht in Position gebracht worden ist. Zeitkomplexität: O (nm)
• Wie oben, aber zuerst den Inhalt von setzen A in eine effiziente Lookupstruktur die lineare Suche zu vermeiden. Zeitkomplexität: O (n + m) unter der Annahme, O (1) Lookup
• Sortieren B . Dann wird für jedes Element in A findet den Index (der exist gewährleistet ist) innerhalb von B mit binärer Suche. Nimm diesen Index in einer Hilfsgruppe die gleiche Größe wie A . Verwenden Sie die Anordnung von Indizes als Eingabe in einen Komparator, der Art A . Zeitkomplexität: O ((m log m) + (n log n) + (n log n))