Hier ist die Frage (Link: Ссылка ):
Eine Permutation der Zahlen 1, ..., N ist eine Neuordnung dieser Zahlen. Zum Beispiel
2 4 5 1 7 6 3 8
ist eine Permutation von 1,2, ..., 8. Natürlich,
1 2 3 4 5 6 7 8
ist auch eine Permutation von 1, 2, ..., 8.
Mit jeder Permutation von N ist eine spezielle Folge von positiven ganzen Zahlen der Länge N verbunden, die als Inversionsfolge bezeichnet wird. Das i-te Element dieser Sequenz ist die Anzahl der Zahlen j, die streng kleiner als i sind und in dieser Permutation rechts von i erscheinen. Für die Permutation
2 4 5 1 7 6 3 8
die Inversionsfolge ist
0 1 0 2 2 1 2 0
Das zweite Element ist 1, weil 1 streng kleiner als 2 ist und in dieser Permutation rechts von 2 erscheint. Ähnlich ist das fünfte Element 2, da 1 und 3 streng weniger als 5 sind, aber in dieser Permutation rechts von 5 erscheinen Ein weiteres Beispiel ist die Inversionsfolge der Permutation 8 7 6 5 4 3 2 1
ist
0 1 2 3 4 5 6 7
In diesem Problem erhalten Sie die Inversionsfolge einiger Permutationen. Ihre Aufgabe besteht darin, die Permutation aus dieser Sequenz zu rekonstruieren.
Ich habe diesen Code entwickelt:
%Vor%Es funktioniert gut und gibt 70% der Testfälle korrekt an, überschreitet aber das Zeitlimit für die restlichen. Gibt es einen anderen, schnelleren Algorithmus, um diese Frage zu lösen?
Ihr Algo hat Komplexität O(N^2) Operationen, so dass für Arrays der Größe 10^5 zu viel Zeit benötigt wird. Ich versuche eine bessere Lösung zu beschreiben:
Wir haben N Zahlen. Rufen wir das inverse Array I auf. Um dieses Problem zu lösen, müssen wir wissen, wo K-th position vom Ende der Permutation ist, die noch frei ist (lasst uns diese Funktion F(K) nennen). Zuerst setzen wir die Zahl N auf die Position F(I[N] + 1) und dann die Zahl N-1 auf die Position F(I[N-1] + 1) und so weiter.
F kann wie folgt berechnet werden: deklarieren Sie das Array M der Größe N : 1 1 1 ... 1 , definieren Sie S(X) = M[1] + M[2] + ... + M[X] . S ist bekannt als Präfix sum . F(K) gleich N plus 1 minus so niedrig X that S(X) = K . Jedes Mal, wenn wir die Nummer Z auf Position N + 1 - X(for K = I[Z] + 1) setzen, setzen wir null auf M[X] . Um X schneller als in O(N) time zu finden, kann ich vorschlagen, Binary zu verwenden Indizierte Bäume , um Präfix-Summen in O(logN) time zu berechnen, und Binäre Suche , um solche X zu finden S(X) entspricht einem vordefinierten Wert.
Die Gesamtkomplexität eines solchen Algorithmus ist O(N(log(N))^2) . Das ist
die Implementierung in Ruby (Sie können direkt in ideone damit spielen: Eingabe ändern, Ausgabe ausführen und prüfen):
Lösung mit O(N(log(N))) Zeit existiert auch. Es verwendet eine Art Binärsuchbaum : wir erstellen BST mit den Zahlen 1, 2, 3, ... N auf den Vertices, dann können wir% co_de finden % number by value in K-th und delete Vertexe in O(log(N)) time ebenfalls.
Auch eine Lösung mit std :: set existiert zwar, aber ich kann momentan noch keine finden.
PS. Ich kann Ihnen auch vorschlagen, einige Bücher über Algo und Olimpyads wie Skienna (Programming Challenges) oder Cormen (Einführung in Algorithmen) zu lesen.
PPS.So Entschuldigung für die falsche Lösung, die ich zuvor beschrieben habe
Der teuerste Teil ist offensichtlich die Verschiebung von bis zu 100 000 Elementen in Ihrem Ergebnis-Array.
Wenn Sie dieses Array in mehrere Blöcke aufteilen, können Sie es um einen signifikanten Faktor beschleunigen.
Wenn Sie 10 Chunks sagen und sich die Anzahl der Elemente für jeden Chunk merken, wählen Sie den richtigen Chunk aus, um entsprechend dem Schlüssel zu schreiben und müssen dann Elemente nur für diesen Chunk verschieben (bis zu 10 mal weniger).
Das neue Problem ist, wie man eine gute Verteilung von Zahlen über die Brocken erreicht.
Sie können auch die verknüpfte Liste verwenden: Ссылка
Es ist sehr effektiv bei Insertionen, aber saugt für zufällige Suche. Aber immer noch suchen ist nur Leseoperation, also könnte das Suchen von x Elementen schneller sein (IDK) als das Verschieben von x Elementen im Array.
Dann könnten Sie einen kombinierten Ansatz verwenden und die Liste mit mehreren Zeigern verknüpfen, so dass Sie immer nach dem nächsten suchen können.
Hier ist ein wirklich guter Algorithmus zusammen mit der erforderlichen Kodierung in C ++:
Das Problem wird mit der Tatsache gelöst, dass, wenn 2 an Stelle 7 ist, zwei leere Kästchen bleiben vor dem Platzieren von 7. Also, wenn 0 bei 8 ist, und 2 bei 7, dann sieht das umgekehrte Ergebnis-Array aus wie: 8 _ _ 7 _ _ _ _.
Nun wird die Quadratwurzelzerlegung durchgeführt und die Einfügung erfolgt:
%Vor%Ihr Algorithmus ist für dieses Problem nicht effizient, weil Ihre Komplexität O (n ^ 2) ist, was 10 ^ 10 Operationen für einige der Eingabefälle bedeutet. Sie müssen eine Lösung finden, die billiger ist.
Ich schlage Ihnen den folgenden Algorithmus vor (Indizes von 1 bis N):
%Vor%