Gegeben ein Array der Größe 3n des Formulars
%Vor% Konvertiere es in [x1, y1, z1, x2, y2, z2, ... xn, yn, zn]
Hier können xn, yn, zn ganze Zahlen sein. Siehe Beispieleingabe und -ausgabe unten.
Zwei Einschränkungen
Eine Beispieleingabe und -ausgabe sind wie folgt.
Eingabe:
[5, 8, 11, 3, 2, 17, 21, 1, 9] 3n = 9. Also n = 3.
Hier
x1=5 x2=8 x3=11 y1=3 y2=2 y3=17 z1=21 z2=1 z3=9
Ausgabe:
[5, 3, 21, 8, 2, 1, 11, 17, 9]
Eine mögliche O (n log n) Lösung: Betrachte nur x's und y's. Jetzt kann ich alle Y's zu seiner Position tauschen, was dazu führen wird, dass x2, x4, x6 aus der Position getauscht werden. Dann werde ich in x2, x4 tauschen, was x3, x7 aus der Position bleibt. Und die nächste Iteration wäre x8, x16. Dies würde mich zu O (n log n) bringen, aber nicht zu O (n).
Da David anscheinend nicht daran interessiert ist, es niederzuschreiben (offensichtlich ist er ist interessiert, siehe die andere Antwort :), werde ich seine Referenz , um zu einem Algorithmus für den Fall mit 3 Partitionen zu gelangen.
Bitte beachten Sie, dass, wenn wir das Problem für einige m & lt; n können wir mit Hilfe eines Algorithmus A das Array neu anordnen, so dass wir A anwenden können und dann ein kleineres Teilproblem haben. Angenommen, das ursprüngliche Array ist
%Vor%Wir möchten es in
umordnen %Vor% Dies ist im Grunde eine Transformation des Musters AaBbCc nach ABCabc , wobei A, B, C und a, b, c jeweils die gleiche Länge haben. Das können wir durch eine Reihe von Umkehrungen erreichen. Sei X 'die Umkehrung der Zeichenkette X hier:
Es gibt wahrscheinlich einen kürzeren Weg, aber das ist immernoch nur eine konstante Anzahl von Operationen, so dass es nur lineare Zeit braucht. Man könnte hier einen ausgefeilteren Algorithmus verwenden, um einige der zyklischen Verschiebungen zu implementieren, aber das ist nur eine Optimierung.
Jetzt können wir die zwei Partitionen unseres Arrays rekursiv lösen und fertig.
Die Frage bleibt, was wäre ein schönes m, das uns den linken Teil leicht lösen lässt?
Um das herauszufinden, müssen wir erkennen, dass wir eine bestimmte Permutation P des Arrays implementieren wollen Indizes. Jede Permutation kann in eine Reihe von Zyklen zerlegt werden a0 -> a1 -> ... -> a{k-1} -> a0 , für die wir P (ai) = a haben {(i + 1)% k}. Es ist einfach, einen solchen Zyklus an Ort und Stelle zu verarbeiten. Der Algorithmus ist auf Wikipedia beschrieben .
Nun besteht das Problem darin, dass Sie, nachdem Sie einen der Zyklen abgeschlossen haben, ein Element finden, das Teil eines Zyklus ist, den Sie noch nicht bearbeitet haben. Es gibt keine generische Lösung dafür, aber für einige bestimmte Permutationen gibt es nette Formeln, die beschreiben, was genau die Positionen sind, die Teil der verschiedenen Zyklen sind.
Für Ihre Probleme wählen Sie einfach m = (5 ^ (2k) - 1) / 3, so dass m & lt; n und k ist maximal. Eine Folge von Elementen, die Teil aller verschiedenen Zyklen sind, ist 5 ^ 0, 5 ^ 1, ..., 5 ^ {k-1}. Sie können diese verwenden, um den Cycle-Leader-Algorithmus auf dem linken Teil des Arrays (nach der Verschiebung) in O (m) zu implementieren.
Wir lösen den übrig gebliebenen rechten Teil rekursiv auf und erhalten einen Algorithmus, um das Problem in der Zeit zu lösen
%Vor%und da m & gt; = Omega (n), erhalten wir T (n) = O (n).
Diese Antwort basiert auf der Arbeit von Peiyush Jain (dessen Bibliografie unglücklich unvollständig ist, aber ich habe keine Lust zu nehmen die Zeit, die Geschichte des In-Place-Umsetzungsproblems zu klären. Beachten Sie, dass 3 eine primitive Wurzel von 25 = 5 ^ 2 ist, da
%Vor%und 20 ist Eulers totient von 25. Nach Jains Theorem 1, einem klassischen Ergebnis der Zahlentheorie, ist 3 eine primitive Wurzel für alle 5 ^ k.
Wenn das Array die Länge 3n hat, ist die neue Position des Elements an der Position k * n + j 3 * j + k. Im Allgemeinen ist die neue Position von i (mit Ausnahme des letzten Elements) (i * n)% (3 * n - 1). Man beachte, dass n die multiplikative Inverse von 3 modulo 3 * n - 1 ist, also 3 eine primitive Wurzel ist, wenn und nur wenn n ist.
Jains Beobachtung ist in diesem Fall, dass, wenn 3 * n - 1 eine Potenz von 5 ist, die obige Permutation log_5 (3 * n - 1) + 1 verschiedene Zyklen hat, angeführt von 5 ^ k für k von 0 bis log_5 (3 * n - 1). (Dies ist mehr oder weniger die Definition der primitiven Wurzel.) Für jeden Zyklus müssen wir nur den Anführer bewegen, das vom Anführer verdrängte Element bewegen, das durch den vom Anführer verdrängten Element verschobene Element verschieben usw. bis wir zum Anführer zurückkehren.
Für andere Array-Größen, brechen Sie das Array in O (log n) implizite Unterfelder der Längen 3 und eins plus Potenzen von 5, die durch 3 teilbar sind: 126, 3126, 78126, etc. Machen Sie eine Reihe von Rotationen, geometrisch in der Größe abnehmend, um die Subarrays zusammenhängend zu bekommen, dann führe den obigen Algorithmus aus.
Wenn Sie dies tatsächlich implementieren, benchmarken Sie es bitte. Ich habe für den Basisfall von Jains Algorithmus (3 ^ n - 1, Paare statt Tripeln) und festgestellt, dass
Tags und Links algorithm