Also eine Liste sagen b = [b1, b2, b3] Ich möchte in der Lage sein, eine Liste a so zu sortieren, dass alle bi , die auch in a existieren, die gleiche relative Reihenfolge wie in% co_de haben % - den Rest von b 's Elementen allein lassen. Also
b kann natürlich ein Tupel oder eine andere geordnete Struktur sein. Was ich herausgefunden habe
%Vor%ist ungeschickt und O (n ^ 2)
Erstellen Sie zuerst ein Dictionary mit Elementen aus b , wobei der Schlüssel das Element und der Wert sein Index ist. Damit sortieren wir später die übereinstimmenden Elemente in a .
Filtern Sie nun das Objekt aus a , das in diesem dict vorhanden ist, dict liefert O (1) lookup.
Sortieren Sie nun diese Liste gefilterter Elemente und konvertieren Sie sie in einen Iterator.
Wiederholen Sie die Schleife erneut mit a und überprüfen Sie für jedes Element, ob es in dict vorhanden ist, und rufen Sie dann seinen Wert vom Iterator ab. Andernfalls verwenden Sie es wie es ist.
%Vor%
Die Gesamtkomplexität der Zeit wird maximal von (O(len(a)), O(len(b)), O(items_in_a_length log items_in_a_length) sein.
Die angenommene Antwort beantwortet die gestellte Frage, aber mein tatsächliches Problem war ein wenig restriktiver - ich möchte die Artikel in den gleichen relativen Positionen in a so viel wie möglich behalten. Also die angenommene Antwort (und mein ursprünglicher Versuch) würde:
Ich möchte einfach die Out-of-Order-Items "aufblasen", damit sie möglichst wenige ihrer Vorfahren verlieren: [ A, B, C, D, E, Z ] -> [ A, C, D, E, B, Z ] . Beachten Sie, dass E bisher die Vorfahren C und D verlieren würde, während B jetzt nur noch B verliert. Abgeprüft:
Tags und Links python algorithm list python-2.7 sorting