Angenommen, ich habe ein n -dimensionales Array von Ganzzahlen (für n=1 ist es ein Vektor, für n=2 ist es eine rechteckige Matrix, für n=3 ist es ein Parallelepiped usw.). Ich muss Elemente des Arrays neu anordnen, so dass Elemente in jeder Zeile, Spalte usw. in einer nicht abnehmenden Reihenfolge sind.
Ist dies für ein beliebiges Eingabe-Array möglich?
Ja, wenn wir das Array als ein einzelnes Dimensionsfeld mit der gleichen Anzahl von Elementen betrachten und es dann sortieren, indem wir es zurück zum ursprünglichen n-dimensionalen Array zurücklegen, bleibt es sortiert, da für jedes i1,....,i_k,...,i_m : für alle i_k < i_k' :
Wie für die zweite Frage:
Ist die erforderliche Reihenfolge für ein beliebiges Eingabearray eindeutig? Längen in allen Dimensionen?
Nein:
%Vor%Was ist der schnellste Algorithmus, um die erforderliche Reihenfolge zu erstellen?
Eine Lösung wird bereits vorgeschlagen: Betrachte es als großes langes Array und sortiere es.
Komplexität ist O(n_1*n_2*...*n_m*log(n_1*n_2*...*n_m))
Mein Bauch sagt, wenn du es schneller machen könntest, könntest du schneller als O(nlogn) , aber ich habe keinen Beweis für diese Behauptung, also könnte es falsch sein.
Lassen Sie mich mehr über die Idee von Alptigin Jalayr sprechen.
Angenommen, wir haben Zeilen sortiert, also haben wir für die folgenden Daten a <= b und c <= d .
Wenn a größer ist als c , dh c <a , dann gibt uns der Tausch uns c < b seit a <= b und a <=d seit b <= d (wenn b > d , tauschen wir% auch co_de% und b ). Mit einem Wort: Wenn Sie zuerst die Zeilen und dann die Spalten sortieren, können Sie die gewünschte Matrix erhalten.
Tags und Links algorithm arrays sorting multidimensional-array