Wie dreht man ein zweidimensionales Array?

Inspiriert von Raymond Chens Beitrag , sagen Sie, Sie haben ein zweidimensionales 4x4-Array, schreiben Sie eine Funktion, die es um 90 Grad dreht. Raymond verlinkt auf eine Lösung im Pseudocode, aber ich würde gerne einige Dinge aus der realen Welt sehen.

[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]

Wird:

[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]

Update : Nicks Antwort ist die einfachste, aber gibt es eine Möglichkeit, es besser zu machen als n ^ 2? Was wäre, wenn die Matrix 10000x10000 wäre?

Hier ist es in C #

int[,] array = new int[4,4] {
    { 1,2,3,4 },
    { 5,6,7,8 },
    { 9,0,1,2 },
    { 3,4,5,6 }
};

int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
    int[,] ret = new int[n, n];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ret[i, j] = matrix[n - j - 1, i];
        }
    }

    return ret;
}

O (n ^ 2) Zeit- und O (1) Raumalgorithmus (ohne Problemumgehungen und Taschentuch!)

Um +90 drehen:

1. Transponieren
2. Kehren Sie jede Zeile um

Um -90 drehen:

Methode 1 :

1. Transponieren
2. Kehren Sie jede Spalte um

Methode 2:

1. Kehren Sie jede Zeile um
2. Transponieren

Um +180 drehen:

Methode 1 : Zweimal um +90 drehen

Methode 2 : Jede Zeile umkehren und dann jede Spalte umkehren (Transponieren)

Um -180 drehen:

Methode 1 : Zweimal um -90 drehen

Methode 2 : Kehren Sie jede Spalte um und kehren Sie dann jede Zeile um

Methode 3 : Drehen Sie um +180, da sie gleich sind

Ich möchte etwas mehr Details hinzufügen. In dieser Antwort werden Schlüsselkonzepte wiederholt, das Tempo ist langsam und wiederholt sich absichtlich. Die hier bereitgestellte Lösung ist nicht die syntaktisch kompakteste, sie ist jedoch für diejenigen gedacht, die lernen möchten, was Matrixrotation und die daraus resultierende Implementierung sind.

Was ist eine Matrix? Für die Zwecke dieser Antwort ist eine Matrix nur ein Raster, in dem Breite und Höhe gleich sind. Beachten Sie, dass Breite und Höhe einer Matrix unterschiedlich sein können. Der Einfachheit halber werden in diesem Lernprogramm nur Matrizen mit gleicher Breite und Höhe berücksichtigt ( quadratische Matrizen ) . Und ja, Matrizen sind der Plural der Matrix.

Beispielmatrizen sind: 2 × 2, 3 × 3 oder 5 × 5. Oder allgemeiner N × N. Eine 2 × 2-Matrix hat 4 Quadrate, weil 2 × 2 = 4. Eine 5 × 5-Matrix hat 25 Quadrate, weil 5 × 5 = 25. Jedes Quadrat wird als Element oder Eintrag bezeichnet. Wir werden jedes Element mit einem Punkt ( .) in den folgenden Diagrammen darstellen:

2 × 2 Matrix

. .
. .

3 × 3 Matrix

. . .
. . .
. . .

4 × 4 Matrix

. . . .
. . . .
. . . .
. . . .

Was bedeutet es also, eine Matrix zu drehen? Nehmen wir eine 2 × 2-Matrix und geben einige Zahlen in jedes Element ein, damit die Drehung beobachtet werden kann:

0 1
2 3

Wenn wir dies um 90 Grad drehen, erhalten wir:

2 0
3 1

Wir haben die gesamte Matrix buchstäblich einmal nach rechts gedreht, genau wie das Lenkrad eines Autos. Es kann hilfreich sein, die Matrix auf die rechte Seite zu „kippen“. Wir wollen in Python eine Funktion schreiben, die eine Matrix nimmt und sich einmal nach rechts dreht. Die Funktionssignatur lautet:

def rotate(matrix):
    # Algorithm goes here.

Die Matrix wird mithilfe eines zweidimensionalen Arrays definiert:

matrix = [
    [0,1],
    [2,3]
]

Daher greift die erste Indexposition auf die Zeile zu. Die zweite Indexposition greift auf die Spalte zu:

matrix[row][column]

Wir definieren eine Utility-Funktion zum Drucken einer Matrix.

def print_matrix(matrix):
    for row in matrix:
        print row

Eine Methode zum Drehen einer Matrix besteht darin, jeweils eine Schicht zu erstellen. Aber was ist eine Schicht? Denken Sie an eine Zwiebel. Genau wie die Schichten einer Zwiebel bewegen wir uns beim Entfernen jeder Schicht in Richtung Zentrum. Andere Analogien ist a Matroschka-Puppe oder eine Partie Pass-the-Parcel.

Die Breite und Höhe einer Matrix bestimmen die Anzahl der Schichten in dieser Matrix. Verwenden wir für jede Ebene unterschiedliche Symbole:

Eine 2 × 2-Matrix hat 1 Schicht

. .
. .

Eine 3 × 3-Matrix hat 2 Schichten

. . .
. x .
. . .

Eine 4 × 4-Matrix hat 2 Schichten

. . . .
. x x .
. x x .
. . . .

Eine 5 × 5-Matrix hat 3 Schichten

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

Eine 6 × 6-Matrix hat 3 Schichten

. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .

Eine 7 × 7-Matrix hat 4 Schichten

. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .

Möglicherweise stellen Sie fest, dass das Erhöhen der Breite und Höhe einer Matrix um eins nicht immer die Anzahl der Ebenen erhöht. Wenn wir die obigen Matrizen nehmen und die Ebenen und Dimensionen tabellieren, sehen wir, dass die Anzahl der Ebenen alle zwei Inkremente von Breite und Höhe einmal zunimmt:

+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 |      1 |
| 2×2 |      1 |
| 3×3 |      2 |
| 4×4 |      2 |
| 5×5 |      3 |
| 6×6 |      3 |
| 7×7 |      4 |
+-----+--------+

Es müssen jedoch nicht alle Schichten gedreht werden. Eine 1 × 1-Matrix ist vor und nach der Drehung dieselbe. Die zentrale 1 × 1-Schicht ist vor und nach der Drehung immer gleich, egal wie groß die Gesamtmatrix ist:

+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 |      1 |                0 |
| 2×2 |      1 |                1 |
| 3×3 |      2 |                1 |
| 4×4 |      2 |                2 |
| 5×5 |      3 |                2 |
| 6×6 |      3 |                3 |
| 7×7 |      4 |                3 |
+-----+--------+------------------+

Wie können wir angesichts der N × N-Matrix programmgesteuert die Anzahl der Schichten bestimmen, die wir drehen müssen? Wenn wir die Breite oder Höhe durch zwei teilen und den Rest ignorieren, erhalten wir die folgenden Ergebnisse.

+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers |   N/2   |
+-----+--------+------------------+---------+
| 1×1 |      1 |                0 | 1/2 = 0 |
| 2×2 |      1 |                1 | 2/2 = 1 |
| 3×3 |      2 |                1 | 3/2 = 1 |
| 4×4 |      2 |                2 | 4/2 = 2 |
| 5×5 |      3 |                2 | 5/2 = 2 |
| 6×6 |      3 |                3 | 6/2 = 3 |
| 7×7 |      4 |                3 | 7/2 = 3 |
+-----+--------+------------------+---------+

Beachte wie N/2 die Anzahl der Ebenen übereinstimmt, die gedreht werden müssen. Manchmal ist die Anzahl der drehbaren Schichten eins weniger als die Gesamtzahl der Schichten in der Matrix. Dies tritt auf, wenn die innerste Schicht nur aus einem Element (dh einer 1 × 1-Matrix) besteht und daher nicht gedreht werden muss. Es wird einfach ignoriert.

Wir werden diese Informationen zweifellos in unserer Funktion benötigen, um eine Matrix zu drehen. Fügen wir sie jetzt hinzu:

def rotate(matrix):
    size = len(matrix)
    # Rotatable layers only.
    layer_count = size / 2

Jetzt wissen wir, was Ebenen sind und wie wir die Anzahl der Ebenen bestimmen können, die tatsächlich gedreht werden müssen. Wie isolieren wir eine einzelne Ebene, damit wir sie drehen können? Zunächst untersuchen wir eine Matrix von der äußersten Schicht nach innen bis zur innersten Schicht. Eine 5 × 5-Matrix besteht aus insgesamt drei Schichten und zwei Schichten, die gedreht werden müssen:

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

Schauen wir uns zuerst die Spalten an. Die Position der Spalten, die die äußerste Schicht definieren, unter der Annahme, dass wir von 0 zählen, ist 0 und 4:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

0 und 4 sind auch die Positionen der Zeilen für die äußerste Schicht.

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

Dies ist immer der Fall, da Breite und Höhe gleich sind. Daher können wir die Spalten- und Zeilenpositionen einer Ebene mit nur zwei Werten (anstatt vier) definieren.

Wenn Sie nach innen zur zweiten Ebene gehen, sind die Spalten 1 und 3. Und ja, Sie haben es erraten, es ist dasselbe für Zeilen. Es ist wichtig zu verstehen, dass wir die Zeilen- und Spaltenpositionen sowohl erhöhen als auch verringern mussten, wenn wir nach innen zur nächsten Ebene gingen.

+-----------+---------+---------+---------+
|   Layer   |  Rows   | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes     |
| Inner     | 1 and 3 | 1 and 3 | Yes     |
| Innermost | 2       | 2       | No      |
+-----------+---------+---------+---------+

Um jede Ebene zu untersuchen, möchten wir eine Schleife mit sowohl zunehmenden als auch abnehmenden Zählern, die eine Bewegung nach innen darstellen, beginnend mit der äußersten Ebene. Wir nennen dies unsere "Layer-Schleife".

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1
        print 'Layer %d: first: %d, last: %d' % (layer, first, last)

# 5x5 matrix
matrix = [
    [ 0, 1, 2, 3, 4],
    [ 5, 6, 6, 8, 9],
    [10,11,12,13,14],
    [15,16,17,18,19],
    [20,21,22,23,24]
]

rotate(matrix)

Der obige Code durchläuft die Positionen (Zeilen und Spalten) aller Ebenen, die gedreht werden müssen.

Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3

Wir haben jetzt eine Schleife, die die Positionen der Zeilen und Spalten jeder Ebene angibt. Die Variablen firstund lastidentifizieren die Indexposition der ersten und letzten Zeilen und Spalten. Zurück zu unseren Zeilen- und Spaltentabellen:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

So können wir durch die Ebenen einer Matrix navigieren. Jetzt brauchen wir eine Möglichkeit, innerhalb einer Ebene zu navigieren, damit wir Elemente auf dieser Ebene verschieben können. Beachten Sie, dass Elemente niemals von einer Ebene zur anderen "springen", sondern sich innerhalb ihrer jeweiligen Ebenen bewegen.

Durch Drehen jedes Elements in einer Ebene wird die gesamte Ebene gedreht. Durch Drehen aller Ebenen in einer Matrix wird die gesamte Matrix gedreht. Dieser Satz ist sehr wichtig. Bitte versuchen Sie Ihr Bestes, um ihn zu verstehen, bevor Sie fortfahren.

Jetzt brauchen wir eine Möglichkeit, Elemente tatsächlich zu bewegen, dh jedes Element und anschließend die Ebene und letztendlich die Matrix zu drehen. Der Einfachheit halber kehren wir zu einer 3x3-Matrix zurück, die eine drehbare Ebene hat.

0 1 2
3 4 5
6 7 8

Unsere Ebenenschleife enthält die Indizes der ersten und letzten Spalte sowie der ersten und letzten Zeile:

+-----+-------+
| Col | 0 1 2 |
+-----+-------+
|     | 0 1 2 |
|     | 3 4 5 |
|     | 6 7 8 |
+-----+-------+

+-----+-------+
| Row |       |
+-----+-------+
|   0 | 0 1 2 |
|   1 | 3 4 5 |
|   2 | 6 7 8 |
+-----+-------+

Da unsere Matrizen immer quadratisch sind, benötigen wir nur zwei Variablen, firstund lastda die Indexpositionen für Zeilen und Spalten gleich sind.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Our layer loop i=0, i=1, i=2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        # We want to move within a layer here.

Die Variablen first und last können leicht verwendet werden, um auf die vier Ecken einer Matrix zu verweisen. Dies liegt daran, dass die Ecken selbst unter Verwendung verschiedener Permutationen von firstund last(ohne Subtraktion, Addition oder Offset dieser Variablen) definiert werden können:

+---------------+-------------------+-------------+
| Corner        | Position          | 3x3 Values  |
+---------------+-------------------+-------------+
| top left      | (first, first)    | (0,0)       |
| top right     | (first, last)     | (0,2)       |
| bottom right  | (last, last)      | (2,2)       |
| bottom left   | (last, first)     | (2,0)       |
+---------------+-------------------+-------------+

Aus diesem Grund beginnen wir unsere Drehung an den äußeren vier Ecken - wir drehen diese zuerst. Lassen Sie uns sie mit hervorheben *.

* 1 *
3 4 5
* 7 *

Wir wollen jedes *mit *dem rechts davon tauschen . Drucken wir also unsere Ecken aus, die nur mit verschiedenen Permutationen von firstund definiert wurden last:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = (first, first)
        top_right = (first, last)
        bottom_right = (last, last)
        bottom_left = (last, first)

        print 'top_left: %s' % (top_left)
        print 'top_right: %s' % (top_right)
        print 'bottom_right: %s' % (bottom_right)
        print 'bottom_left: %s' % (bottom_left)

matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]

rotate(matrix)

Die Ausgabe sollte sein:

top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)

Jetzt können wir ganz einfach jede der Ecken innerhalb unserer Ebenenschleife vertauschen:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = matrix[first][first]
        top_right = matrix[first][last]
        bottom_right = matrix[last][last]
        bottom_left = matrix[last][first]

        # bottom_left -> top_left
        matrix[first][first] = bottom_left
        # top_left -> top_right
        matrix[first][last] = top_left
        # top_right -> bottom_right
        matrix[last][last] = top_right
        # bottom_right -> bottom_left
        matrix[last][first] = bottom_right


print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)

Matrix vor dem Drehen von Ecken:

[0, 1, 2]
[3, 4, 5]
[6, 7, 8]

Matrix nach rotierenden Ecken:

[6, 1, 0]
[3, 4, 5]
[8, 7, 2]

Toll! Wir haben jede Ecke der Matrix erfolgreich gedreht. Wir haben jedoch die Elemente in der Mitte jeder Ebene nicht gedreht. Natürlich brauchen wir eine Möglichkeit, innerhalb einer Ebene zu iterieren.

Das Problem ist, dass die einzige Schleife in unserer Funktion (unsere Ebenenschleife) bei jeder Iteration zur nächsten Ebene wechselt. Da unsere Matrix nur eine drehbare Ebene hat, wird die Ebenenschleife beendet, nachdem nur die Ecken gedreht wurden. Schauen wir uns an, was mit einer größeren 5 × 5-Matrix passiert (bei der zwei Schichten gedreht werden müssen). Der Funktionscode wurde weggelassen, bleibt aber derselbe wie oben:

matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)

Die Ausgabe ist:

[20,  1,  2,  3,  0]
[ 5, 16,  7,  6,  9]
[10, 11, 12, 13, 14]
[15, 18, 17,  8, 19]
[24, 21, 22, 23,  4]

Es sollte keine Überraschung sein, dass die Ecken der äußersten Ebene gedreht wurden, aber Sie können auch feststellen, dass die Ecken der nächsten Ebene (nach innen) ebenfalls gedreht wurden. Das macht Sinn. Wir haben Code geschrieben, um durch Ebenen zu navigieren und die Ecken jeder Ebene zu drehen. Das fühlt sich nach Fortschritt an, aber leider müssen wir einen Schritt zurücktreten. Es ist einfach nicht gut, zur nächsten Ebene zu wechseln, bis die vorherige (äußere) Ebene vollständig gedreht wurde. Das heißt, bis jedes Element in der Ebene gedreht wurde. Nur die Ecken zu drehen reicht nicht!

Tief durchatmen. Wir brauchen eine andere Schleife. Eine verschachtelte Schleife nicht weniger. Die neue, verschachtelte Schleife wird die Verwendung firstund lastVariablen, plus ein Offset innerhalb einer Schicht zu navigieren. Wir werden diese neue Schleife unsere "Elementschleife" nennen. Die Elementschleife besucht jedes Element in der oberen Reihe, jedes Element auf der rechten Seite, jedes Element in der unteren Reihe und jedes Element auf der linken Seite.

• Wenn Sie in der oberen Zeile vorwärts gehen, muss der Spaltenindex erhöht werden.
• Wenn Sie sich auf der rechten Seite nach unten bewegen, muss der Zeilenindex erhöht werden.
• Wenn Sie sich am unteren Rand rückwärts bewegen, muss der Spaltenindex dekrementiert werden.
• Wenn Sie die linke Seite nach oben bewegen, muss der Zeilenindex dekrementiert werden.

Das klingt komplex, ist aber einfach, da die Häufigkeit, mit der wir inkrementieren und dekrementieren, um das oben Gesagte zu erreichen, auf allen vier Seiten der Matrix gleich bleibt. Zum Beispiel:

• Bewegen Sie 1 Element über die oberste Reihe.
• Bewegen Sie 1 Element auf der rechten Seite nach unten.
• Bewegen Sie 1 Element entlang der unteren Reihe nach hinten.
• Bewegen Sie 1 Element auf der linken Seite nach oben.

Dies bedeutet, dass wir eine einzelne Variable in Kombination mit den Variablen firstund verwenden lastkönnen, um sich innerhalb einer Ebene zu bewegen. Es kann hilfreich sein zu beachten, dass für das Bewegen über die obere Reihe und nach unten auf der rechten Seite ein Inkrementieren erforderlich ist. Während Sie sich entlang der unteren und oberen linken Seite rückwärts bewegen, müssen beide dekrementiert werden.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Move through layers (i.e. layer loop).
    for layer in range(0, layer_count):

            first = layer
            last = size - first - 1

            # Move within a single layer (i.e. element loop).
            for element in range(first, last):

                offset = element - first

                # 'element' increments column (across right)
                top_element = (first, element)
                # 'element' increments row (move down)
                right_side = (element, last)
                # 'last-offset' decrements column (across left)
                bottom = (last, last-offset)
                # 'last-offset' decrements row (move up)
                left_side = (last-offset, first)

                print 'top: %s' % (top)
                print 'right_side: %s' % (right_side)
                print 'bottom: %s' % (bottom)
                print 'left_side: %s' % (left_side)

Jetzt müssen wir nur noch die Oberseite der rechten Seite, die rechte Seite der Unterseite, die Unterseite der linken Seite und die linke Seite der Oberseite zuweisen. Wenn wir das alles zusammenfügen, erhalten wir:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1

        for element in range(first, last):
            offset = element - first

            top = matrix[first][element]
            right_side = matrix[element][last]
            bottom = matrix[last][last-offset]
            left_side = matrix[last-offset][first]

            matrix[first][element] = left_side
            matrix[element][last] = top
            matrix[last][last-offset] = right_side
            matrix[last-offset][first] = bottom

Angesichts der Matrix:

0,  1,  2  
3,  4,  5  
6,  7,  8 

Unsere rotateFunktion ergibt:

6,  3,  0  
7,  4,  1  
8,  5,  2  

Python:

rotated = list(zip(*original[::-1]))

und gegen den Uhrzeigersinn:

rotated_ccw = list(zip(*original))[::-1]

So funktioniert das:

zip(*original)tauscht Achsen von 2D-Arrays aus, indem entsprechende Elemente aus Listen in neue Listen gestapelt werden. (Der *Operator weist die Funktion an, die enthaltenen Listen in Argumente zu verteilen.)

>>> list(zip(*[[1,2,3],[4,5,6],[7,8,9]]))
[[1,4,7],[2,5,8],[3,6,9]]

Die [::-1]Anweisung kehrt Array-Elemente um (siehe Extended Slices oder diese Frage ):

>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]

Schließlich führt die Kombination der beiden zur Rotationstransformation.

Durch die Änderung der Platzierung von [::-1]werden Listen in verschiedenen Ebenen der Matrix umgekehrt.

Hier ist eine, die die Drehung an Ort und Stelle ausführt, anstatt ein völlig neues Array zu verwenden, um das Ergebnis zu speichern. Ich habe die Initialisierung des Arrays abgebrochen und ausgedruckt. Dies funktioniert nur für quadratische Arrays, sie können jedoch beliebig groß sein. Der Speicheraufwand entspricht der Größe eines Elements des Arrays, sodass Sie ein beliebig großes Array drehen können.

int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
    for (int j = i; j < n - i - 1; j++)
    {
        tmp             = a[i][j];
        a[i][j]         = a[j][n-i-1];
        a[j][n-i-1]     = a[n-i-1][n-j-1];
        a[n-i-1][n-j-1] = a[n-j-1][i];
        a[n-j-1][i]     = tmp;
    }
}

Es gibt hier jede Menge guten Codes, aber ich möchte nur zeigen, was geometrisch vor sich geht, damit Sie die Codelogik ein wenig besser verstehen können. Hier ist, wie ich das angehen würde.

Verwechseln Sie dies zunächst nicht mit einer sehr einfachen Umsetzung.

Die Grundidee ist, es als Schichten zu behandeln und wir drehen jeweils eine Schicht nach der anderen.

Sagen wir, wir haben einen 4x4

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

Nachdem wir es um 90 im Uhrzeigersinn gedreht haben, erhalten wir

13  9   5   1
14  10  6   2   
15  11  7   3
16  12  8   4

Zerlegen wir dies also. Zuerst drehen wir die 4 Ecken im Wesentlichen

1           4


13          16

dann drehen wir den folgenden Diamanten, der irgendwie schief ist

    2
            8
9       
        15

und dann der 2. schiefe Diamant

        3
5           
            12
    14

Das kümmert sich also um die Außenkante, so dass wir im Wesentlichen diese eine Schale nach der anderen machen, bis

schließlich das mittlere Quadrat (oder wenn es seltsam ist, nur das letzte Element, das sich nicht bewegt)

6   7
10  11

Lassen Sie uns nun die Indizes jeder Ebene herausfinden. Nehmen wir an, wir arbeiten immer mit der äußersten Ebene, die wir gerade ausführen

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

so weiter und so fort, bis wir auf halbem Weg sind

so ist im Allgemeinen das Muster

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

Wie ich in meinem vorherigen Beitrag sagte, ist hier ein Code in C #, der eine O (1) -Matrixrotation für eine Matrix beliebiger Größe implementiert. Der Kürze und Lesbarkeit halber gibt es keine Fehler- oder Bereichsprüfung. Der Code:

static void Main (string [] args)
{
  int [,]
    //  create an arbitrary matrix
    m = {{0, 1}, {2, 3}, {4, 5}};

  Matrix
    //  create wrappers for the data
    m1 = new Matrix (m),
    m2 = new Matrix (m),
    m3 = new Matrix (m);

  //  rotate the matricies in various ways - all are O(1)
  m1.RotateClockwise90 ();
  m2.Rotate180 ();
  m3.RotateAnitclockwise90 ();

  //  output the result of transforms
  System.Diagnostics.Trace.WriteLine (m1.ToString ());
  System.Diagnostics.Trace.WriteLine (m2.ToString ());
  System.Diagnostics.Trace.WriteLine (m3.ToString ());
}

class Matrix
{
  enum Rotation
  {
    None,
    Clockwise90,
    Clockwise180,
    Clockwise270
  }

  public Matrix (int [,] matrix)
  {
    m_matrix = matrix;
    m_rotation = Rotation.None;
  }

  //  the transformation routines
  public void RotateClockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
  }

  public void Rotate180 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
  }

  public void RotateAnitclockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
  }

  //  accessor property to make class look like a two dimensional array
  public int this [int row, int column]
  {
    get
    {
      int
        value = 0;

      switch (m_rotation)
      {
      case Rotation.None:
        value = m_matrix [row, column];
        break;

      case Rotation.Clockwise90:
        value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
        break;

      case Rotation.Clockwise180:
        value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
        break;

      case Rotation.Clockwise270:
        value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
        break;
      }

      return value;
    }

    set
    {
      switch (m_rotation)
      {
      case Rotation.None:
        m_matrix [row, column] = value;
        break;

      case Rotation.Clockwise90:
        m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
        break;

      case Rotation.Clockwise180:
        m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
        break;

      case Rotation.Clockwise270:
        m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
        break;
      }
    }
  }

  //  creates a string with the matrix values
  public override string ToString ()
  {
    int
      num_rows = 0,
      num_columns = 0;

    switch (m_rotation)
    {
    case Rotation.None:
    case Rotation.Clockwise180:
      num_rows = m_matrix.GetUpperBound (0);
      num_columns = m_matrix.GetUpperBound (1);
      break;

    case Rotation.Clockwise90:
    case Rotation.Clockwise270:
      num_rows = m_matrix.GetUpperBound (1);
      num_columns = m_matrix.GetUpperBound (0);
      break;
    }

    StringBuilder
      output = new StringBuilder ();

    output.Append ("{");

    for (int row = 0 ; row <= num_rows ; ++row)
    {
      if (row != 0)
      {
        output.Append (", ");
      }

      output.Append ("{");

      for (int column = 0 ; column <= num_columns ; ++column)
      {
        if (column != 0)
        {
          output.Append (", ");
        }

        output.Append (this [row, column].ToString ());
      }

      output.Append ("}");
    }

    output.Append ("}");

    return output.ToString ();
  }

  int [,]
    //  the original matrix
    m_matrix;

  Rotation
    //  the current view of the matrix
    m_rotation;
}

OK, ich werde meine Hand heben, es werden beim Drehen keine Änderungen am ursprünglichen Array vorgenommen. In einem OO-System spielt dies jedoch keine Rolle, solange das Objekt so aussieht, als wäre es für die Clients der Klasse gedreht worden. Im Moment verwendet die Matrix-Klasse Verweise auf die ursprünglichen Array-Daten, sodass durch Ändern eines beliebigen Werts von m1 auch m2 und m3 geändert werden. Eine kleine Änderung am Konstruktor, um ein neues Array zu erstellen und die Werte dorthin zu kopieren, wird das klären.

Während das Drehen der Daten an Ort und Stelle erforderlich sein kann (möglicherweise um die physisch gespeicherte Darstellung zu aktualisieren), wird es einfacher und möglicherweise leistungsfähiger, dem Arrayzugriff eine Indirektionsebene hinzuzufügen, möglicherweise eine Schnittstelle:

interface IReadableMatrix
{
    int GetValue(int x, int y);
}

Wenn Sie Matrixdiese Schnittstelle bereits implementiert haben, kann sie über eine Dekorationsklasse wie die folgende gedreht werden :

class RotatedMatrix : IReadableMatrix
{
    private readonly IReadableMatrix _baseMatrix;

    public RotatedMatrix(IReadableMatrix baseMatrix)
    {
        _baseMatrix = baseMatrix;
    }

    int GetValue(int x, int y)
    {
        // transpose x and y dimensions
        return _baseMatrix(y, x);
    }
}

Auf diese Weise können auch + 90 / -90 / 180 Grad gedreht, horizontal / vertikal gespiegelt und skaliert werden.

Die Leistung müsste in Ihrem spezifischen Szenario gemessen werden. Die O (n ^ 2) -Operation wurde jetzt jedoch durch einen O (1) -Aufruf ersetzt. Es ist eine virtuelle Call - Methode , die ist langsamer als die direkte Array - Zugriff, so hängt es davon ab, wie häufig die gedrehte Anordnung nach der Drehung verwendet wird. Wenn es einmal verwendet wird, würde dieser Ansatz definitiv gewinnen. Wenn es gedreht und dann tagelang in einem System mit langer Laufzeit verwendet wird, ist die Rotation an Ort und Stelle möglicherweise besser. Es hängt auch davon ab, ob Sie die Vorabkosten akzeptieren können.

Wie bei allen Leistungsproblemen messen, messen, messen!

Dies ist eine bessere Version davon in Java: Ich habe es für eine Matrix mit einer anderen Breite und Höhe gemacht

• h ist hier die Höhe der Matrix nach dem Drehen
• w ist hier die Breite der Matrix nach dem Drehen

public int[][] rotateMatrixRight(int[][] matrix)
{
    /* W and H are already swapped */
    int w = matrix.length;
    int h = matrix[0].length;
    int[][] ret = new int[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ret[i][j] = matrix[w - j - 1][i];
        }
    }
    return ret;
}


public int[][] rotateMatrixLeft(int[][] matrix)
{
    /* W and H are already swapped */
    int w = matrix.length;
    int h = matrix[0].length;   
    int[][] ret = new int[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            ret[i][j] = matrix[j][h - i - 1];
        }
    }
    return ret;
}

Dieser Code basiert auf dem Beitrag von Nick Berardi.

Rubinweg: .transpose.map &:reverse

Es gibt bereits viele Antworten, und ich habe zwei gefunden, die O (1) -Zeitkomplexität beanspruchen. Der eigentliche O (1) -Algorithmus besteht darin, den Array-Speicher unberührt zu lassen und die Indizierung seiner Elemente zu ändern. Das Ziel hierbei ist, dass es weder zusätzlichen Speicher verbraucht noch zusätzliche Zeit benötigt, um die Daten zu iterieren.

Drehungen von 90, -90 und 180 Grad sind einfache Transformationen, die ausgeführt werden können, solange Sie wissen, wie viele Zeilen und Spalten sich in Ihrem 2D-Array befinden. Um einen Vektor um 90 Grad zu drehen, tauschen Sie die Achsen und negieren Sie die Y-Achse. Vertauschen Sie für -90 Grad die Achsen und negieren Sie die X-Achse. Negieren Sie für 180 Grad beide Achsen ohne zu tauschen.

Weitere Transformationen sind möglich, z. B. horizontales und / oder vertikales Spiegeln, indem die Achsen unabhängig voneinander negiert werden.

Dies kann beispielsweise durch eine Zugriffsmethode erfolgen. Die folgenden Beispiele sind JavaScript-Funktionen, die Konzepte gelten jedoch für alle Sprachen gleichermaßen.

 // Get an array element in column/row order
 var getArray2d = function(a, x, y) {
   return a[y][x];
 };

 //demo
 var arr = [
   [5, 4, 6],
   [1, 7, 9],
   [-2, 11, 0],
   [8, 21, -3],
   [3, -1, 2]
 ];

 var newarr = [];
 arr[0].forEach(() => newarr.push(new Array(arr.length)));

 for (var i = 0; i < newarr.length; i++) {
   for (var j = 0; j < newarr[0].length; j++) {
     newarr[i][j] = getArray2d(arr, i, j);
   }
 }
 console.log(newarr);

// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
  var t = x;
  x = y;
  y = a.length - t - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
  var t = x;
  x = a[0].length - y - 1;
  y = t;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
  x = a[0].length - x - 1;
  y = a.length - y - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2d180(arr, i, j);
  }
}
console.log(newarr);

Dieser Code setzt ein Array verschachtelter Arrays voraus, wobei jedes innere Array eine Zeile ist.

Mit dieser Methode können Sie Elemente (auch in zufälliger Reihenfolge) lesen (oder schreiben), als ob das Array gedreht oder transformiert worden wäre. Wählen Sie jetzt einfach die richtige Funktion zum Aufrufen aus, wahrscheinlich als Referenz, und los geht's!

Das Konzept kann erweitert werden, um Transformationen additiv (und zerstörungsfrei) über die Zugriffsmethoden anzuwenden. Einschließlich beliebiger Winkelrotationen und Skalierung.

Einige Leute haben bereits Beispiele angeführt, bei denen ein neues Array erstellt wird.

Ein paar andere Dinge zu beachten:

(a) Anstatt die Daten tatsächlich zu verschieben, durchlaufen Sie das "gedrehte" Array einfach anders.

(b) Das Drehen an Ort und Stelle kann etwas schwieriger sein. Sie benötigen ein wenig Kratzer (wahrscheinlich ungefähr gleich einer Zeile oder Spalte). Es gibt ein altes ACM-Papier über das Durchführen von Transponierungen an Ort und Stelle ( http://doi.acm.org/10.1145/355719.355729 ), aber ihr Beispielcode ist böses, mit GOTO beladenes FORTRAN.

Nachtrag:

http://doi.acm.org/10.1145/355611.355612 ist ein weiterer, angeblich überlegener Transponierungsalgorithmus an Ort und Stelle.

Nicks Antwort würde auch für ein NxM-Array mit nur einer kleinen Modifikation funktionieren (im Gegensatz zu einem NxN).

string[,] orig = new string[n, m];
string[,] rot = new string[m, n];

...

for ( int i=0; i < n; i++ )
  for ( int j=0; j < m; j++ )
    rot[j, n - i - 1] = orig[i, j];

Eine Möglichkeit, darüber nachzudenken, besteht darin, dass Sie den Mittelpunkt der Achse (0,0) von der oberen linken Ecke zur oberen rechten Ecke verschoben haben. Sie transponieren einfach von einem zum anderen.

Zeit - O (N), Raum - O (1)

public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2; i++) {
        int last = n - 1 - i;
        for (int j = i; j < last; j++) {
            int top = matrix[i][j];
            matrix[i][j] = matrix[last - j][i];
            matrix[last - j][i] = matrix[last][last - j];
            matrix[last][last - j] = matrix[j][last];
            matrix[j][last] = top;
        }
    }
}

Hier ist meine Ruby-Version (beachten Sie, dass die Werte nicht gleich angezeigt werden, sie sich jedoch wie beschrieben drehen).

def rotate(matrix)
  result = []
  4.times { |x|
    result[x] = []
    4.times { |y|
      result[x][y] = matrix[y][3 - x]
    }
  }

  result
end

matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]

def print_matrix(matrix)
  4.times { |y|
    4.times { |x|
      print "#{matrix[x][y]} "
    }
    puts ""
  }
end

print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))

Die Ausgabe:

1 5 9 3 
2 6 0 4 
3 7 1 5 
4 8 2 6 

4 3 2 1 
8 7 6 5 
2 1 0 9 
6 5 4 3

Hier ist eine In-Space-Rotationsmethode von Java, nur für Quadrat. Für nicht quadratische 2D-Arrays müssen Sie ohnehin ein neues Array erstellen.

private void rotateInSpace(int[][] arr) {
    int z = arr.length;
    for (int i = 0; i < z / 2; i++) {
        for (int j = 0; j < (z / 2 + z % 2); j++) {
            int x = i, y = j;
            int temp = arr[x][y];
            for (int k = 0; k < 4; k++) {
                int temptemp = arr[y][z - x - 1];
                arr[y][z - x - 1] = temp;
                temp = temptemp;

                int tempX = y;
                y = z - x - 1;
                x = tempX;
            }
        }
    }
}

Code zum Drehen eines 2D-Arrays beliebiger Größe durch Erstellen eines neuen Arrays:

private int[][] rotate(int[][] arr) {
    int width = arr[0].length;
    int depth = arr.length;
    int[][] re = new int[width][depth];
    for (int i = 0; i < depth; i++) {
        for (int j = 0; j < width; j++) {
            re[j][depth - i - 1] = arr[i][j];
        }
    }
    return re;
}

Implementierung des +90-Pseudocodes von dimple (z. B. transponieren und dann jede Zeile umkehren) in JavaScript:

function rotate90(a){
  // transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
  a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
  // row reverse
  for (i in a){
    a[i] = a[i].reverse();
  }
  return a;
}

Sie können dies in 3 einfachen Schritten tun :

1 ) Angenommen, wir haben eine Matrix

   1 2 3
   4 5 6
   7 8 9

2 ) Nehmen Sie die Transponierte der Matrix

   1 4 7
   2 5 8
   3 6 9

3 ) Vertauschen Sie die Zeilen, um eine gedrehte Matrix zu erhalten

   3 6 9
   2 5 8
   1 4 7

Java- Quellcode dafür:

public class MyClass {

    public static void main(String args[]) {
        Demo obj = new Demo();
        /*initial matrix to rotate*/
        int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[][] transpose = new int[3][3]; // matrix to store transpose

        obj.display(matrix);              // initial matrix

        obj.rotate(matrix, transpose);    // call rotate method
        System.out.println();
        obj.display(transpose);           // display the rotated matix
    }
}

class Demo {   
    public void rotate(int[][] mat, int[][] tran) {

        /* First take the transpose of the matrix */
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat.length; j++) {
                tran[i][j] = mat[j][i]; 
            }
        }

        /*
         * Interchange the rows of the transpose matrix to get rotated
         * matrix
         */
        for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
            for (int k = 0; k < tran.length; k++) {
                swap(i, k, j, k, tran);
            }
        }
    }

    public void swap(int a, int b, int c, int d, int[][] arr) {
        int temp = arr[a][b];
        arr[a][b] = arr[c][d];
        arr[c][d] = temp;    
    }

    /* Method to display the matrix */
    public void display(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Ausgabe:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 

Dies ist meine Implementierung in C, O (1) -Speicherkomplexität an Ort und Stelle um 90 Grad im Uhrzeigersinn:

#include <stdio.h>

#define M_SIZE 5

static void initMatrix();
static void printMatrix();
static void rotateMatrix();

static int m[M_SIZE][M_SIZE];

int main(void){
    initMatrix();
    printMatrix();
    rotateMatrix();
    printMatrix();

    return 0;
}

static void initMatrix(){
    int i, j;

    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            m[i][j] = M_SIZE*i + j + 1;
        }
    }
}

static void printMatrix(){
    int i, j;

    printf("Matrix\n");
    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            printf("%02d ", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

static void rotateMatrix(){
    int r, c;

    for(r = 0; r < M_SIZE/2; r++){
        for(c = r; c < M_SIZE - r - 1; c++){
            int tmp = m[r][c];

            m[r][c] = m[M_SIZE - c - 1][r];
            m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
            m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
            m[c][M_SIZE - r - 1] = tmp;
        }
    }
}

Hier ist die Java-Version:

public static void rightRotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer;
        int last = n - 1 - first;
        for (int i = first; i < last; i++) {
           int offset = i - first;
           int temp = matrix[first][i];
           matrix[first][i] = matrix[last-offset][first];
           matrix[last-offset][first] = matrix[last][last-offset];
           matrix[last][last-offset] = matrix[i][last];
           matrix[i][last] = temp;
        }
    }
}

Bei dieser Methode wird zuerst die äußerste Schicht gedreht und dann die innere Schicht nach rechts verschoben.

Betrachten Sie aus linearer Sicht die Matrizen:

    1 2 3        0 0 1
A = 4 5 6    B = 0 1 0
    7 8 9        1 0 0

Nehmen Sie jetzt eine Transponierte

     1 4 7
A' = 2 5 8
     3 6 9

Und betrachten Sie die Aktion von A 'auf B oder B auf A'.
Beziehungsweise:

      7 4 1          3 6 9
A'B = 8 5 2    BA' = 2 5 8
      9 6 3          1 4 7

Dies ist für jede nxn-Matrix erweiterbar. Und dieses Konzept schnell im Code anwenden:

void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
    mat[r1][c1] ^= mat[r2][c2];
    mat[r2][c2] ^= mat[r1][c1];
    mat[r1][c1] ^= mat[r2][c2];
}

void transpose(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = (i + 1); j < size; j++)
        {
            swapInSpace(mat, i, j, j, i);
        }
    }
}

void rotate(int** mat, int size)
{
    //Get transpose
    transpose(mat, size);

    //Swap columns
    for (int i = 0; i < size / 2; i++)
    {
        for (int j = 0; j < size; j++)
        {
            swapInSpace(mat, i, j, size - (i + 1), j);
        }
    }
}

C # -Code zum Drehen von [n, m] 2D-Arrays um 90 Grad nach rechts

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MatrixProject
{
    // mattrix class

    class Matrix{
        private int rows;
        private int cols;
        private int[,] matrix;

        public Matrix(int n){
            this.rows = n;
            this.cols = n;
            this.matrix = new int[this.rows,this.cols];

        }

        public Matrix(int n,int m){
            this.rows = n;
            this.cols = m;

            this.matrix = new int[this.rows,this.cols];
        }

        public void Show()
        {
            for (var i = 0; i < this.rows; i++)
            {
                for (var j = 0; j < this.cols; j++) {
                    Console.Write("{0,3}", this.matrix[i, j]);
                }
                Console.WriteLine();
            }                
        }

        public void ReadElements()
        {
           for (var i = 0; i < this.rows; i++)
                for (var j = 0; j < this.cols; j++)
                {
                    Console.Write("element[{0},{1}]=",i,j);
                    this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
                }            
        }


        // rotate [n,m] 2D array by 90 deg right
        public void Rotate90DegRight()
        {

            // create a mirror of current matrix
            int[,] mirror = this.matrix;

            // create a new matrix
            this.matrix = new int[this.cols, this.rows];

            for (int i = 0; i < this.rows; i++)
            {
                for (int j = 0; j < this.cols; j++)
                {
                    this.matrix[j, this.rows - i - 1] = mirror[i, j];
                }
            }

            // replace cols count with rows count
            int tmp = this.rows;
            this.rows = this.cols;
            this.cols = tmp;           
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Matrix myMatrix = new Matrix(3,4);
            Console.WriteLine("Enter matrix elements:");
            myMatrix.ReadElements();
            Console.WriteLine("Matrix elements are:");
            myMatrix.Show();
            myMatrix.Rotate90DegRight();
            Console.WriteLine("Matrix rotated at 90 deg are:");
            myMatrix.Show();
            Console.ReadLine();
        }
    }
}

Ergebnis:

    Enter matrix elements:
    element[0,0]=1
    element[0,1]=2
    element[0,2]=3
    element[0,3]=4
    element[1,0]=5
    element[1,1]=6
    element[1,2]=7
    element[1,3]=8
    element[2,0]=9
    element[2,1]=10
    element[2,2]=11
    element[2,3]=12
    Matrix elements are:
      1  2  3  4
      5  6  7  8
      9 10 11 12
    Matrix rotated at 90 deg are:
      9  5  1
     10  6  2
     11  7  3
     12  8  4

PHP:

<?php    
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result

while(count($a)>0)
{
    $b[count($a[0])-1][] = array_shift($a[0]);
    if (count($a[0])==0)
    {
         array_shift($a);
    }
}

Ab PHP5.6 kann die Array-Transposition mit einem Sleak durchgeführt werden array_map() Aufruf durchgeführt werden. Mit anderen Worten, Spalten werden in Zeilen konvertiert.

Code: ( Demo )

$array = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 0, 1, 2],
    [3, 4, 5, 6]
];
$transposed = array_map(null, ...$array);

$ transponiert:

[
    [1, 5, 9, 3],
    [2, 6, 0, 4],
    [3, 7, 1, 5],
    [4, 8, 2, 6]
]

For i:= 0 to X do For j := 0 to X do graphic[j][i] := graphic2[X-i][j]

X ist die Größe des Arrays, in dem sich die Grafik befindet.

#transpose ist eine Standardmethode der Ruby-Array-Klasse.

% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] 
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]

Die Implementierung ist eine in C geschriebene n ^ 2-Transpositionsfunktion. Sie können sie hier sehen: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose durch Auswahl von "click" Quelle "neben" transponieren "umschalten.

Ich erinnere mich besser als O (n ^ 2) -Lösungen, aber nur für speziell konstruierte Matrizen (wie spärliche Matrizen)

C-Code für die Matrixdrehung um 90 Grad im Uhrzeigersinn IN PLACE für jede M * N-Matrix

void rotateInPlace(int * arr[size][size], int row, int column){
    int i, j;
    int temp = row>column?row:column;
    int flipTill = row < column ? row : column;
    for(i=0;i<flipTill;i++){
        for(j=0;j<i;j++){
            swapArrayElements(arr, i, j);
        }
    }

    temp = j+1;

    for(i = row>column?i:0; i<row; i++){
            for(j=row<column?temp:0; j<column; j++){
                swapArrayElements(arr, i, j);
            }
    }

    for(i=0;i<column;i++){
        for(j=0;j<row/2;j++){
            temp = arr[i][j];
            arr[i][j] = arr[i][row-j-1];
            arr[i][row-j-1] = temp;
        }
    }
}

Hier ist meine In-Place-Implementierung in C.

void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}

Hier ist mein Versuch einer Matrix-90-Grad-Drehung, die eine 2-Stufen-Lösung in C ist. Transponieren Sie zuerst die Matrix an Ort und Stelle und tauschen Sie dann die Spalten aus.

#define ROWS        5
#define COLS        5

void print_matrix_b(int B[][COLS], int rows, int cols) 
{
    for (int i = 0; i <= rows; i++) {
        for (int j = 0; j <=cols; j++) {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }
}

void swap_columns(int B[][COLS], int l, int r, int rows)
{
    int tmp;
    for (int i = 0; i <= rows; i++) {
        tmp = B[i][l];
        B[i][l] = B[i][r];
        B[i][r] = tmp;
    }
}


void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
    int tmp;
    // Transpose the matrix first
    for (int i = 0; i <= rows; i++) {
        for (int j = i; j <=cols; j++) {
            tmp = B[i][j];
            B[i][j] = B[j][i];
            B[j][i] = tmp;
        }
    }
    // Swap the first and last col and continue until
    // the middle.
    for (int i = 0; i < (cols / 2); i++)
        swap_columns(B, i, cols - i, rows);
}



int _tmain(int argc, _TCHAR* argv[])
{
    int B[ROWS][COLS] = { 
                  {1, 2, 3, 4, 5}, 
                      {6, 7, 8, 9, 10},
                          {11, 12, 13, 14, 15},
                          {16, 17, 18, 19, 20},
                          {21, 22, 23, 24, 25}
                        };

    matrix_2d_rotation(B, ROWS - 1, COLS - 1);

    print_matrix_b(B, ROWS - 1, COLS -1);
    return 0;
}

@ Tagorym: Aw, Mann. Ich hatte daran als gutes "Ich bin gelangweilt, was kann ich denken" -Puzzlespiel festgehalten. Ich habe mir meinen Transpositionscode ausgedacht, bin aber hierher gekommen, um Ihren Code zu finden, der ziemlich identisch mit meinem ist ... ah, na ja. Hier ist es in Ruby.

require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }

pp a

0.upto(n/2-1) do |i|
  i.upto(n-i-2) do |j|
    tmp             = a[i][j]
    a[i][j]         = a[n-j-1][i]
    a[n-j-1][i]     = a[n-i-1][n-j-1]
    a[n-i-1][n-j-1] = a[j][n-i-1]
    a[j][n-i-1]     = tmp
  end
end

pp a

short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};

short rotated[4][4];

for (int r = 0; r < 4; ++r)
{
  for (int c = 0; c < 4; ++c)
  {
    rotated[r][c] = normal[c][3-r];
  }
}

Einfache C ++ - Methode, obwohl in einem großen Array ein großer Speicheraufwand anfällt.