Wie dreht man ein zweidimensionales Array?

StackOverflow https://stackoverflow.com/questions/42519

Frage

Inspiriert von Raymond Chens Beitrag, Angenommen, 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 etwas 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]

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

War es hilfreich?

Lösung

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;
}

Andere Tipps

O(n^2)-Zeit- und O(1)-Raumalgorithmus (ohne Workarounds und Taschentücher!)

Um +90 drehen:

  1. Transponieren
  2. Drehen Sie jede Reihe um

Um -90 drehen:

Methode 1 :

  1. Transponieren
  2. Kehren Sie jede Spalte um

Methode 2:

  1. Drehen Sie jede Reihe 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:Um +180 drehen, da sie gleich sind

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

Erstens: Was ist eine Matrix?Für die Zwecke dieser Antwort ist eine Matrix nur ein Raster, dessen Breite und Höhe gleich sind.Beachten Sie, dass die Breite und Höhe einer Matrix unterschiedlich sein können. Der Einfachheit halber werden in diesem Tutorial jedoch nur Matrizen mit gleicher Breite und Höhe berücksichtigt (quadratische Matrizen).Und ja, Matrizen ist der Plural von 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 darstellen (.) in den folgenden Diagrammen:

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 in jedes Element einige Zahlen ein, damit die Rotation 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, daran zu denken, die Matrix auf die rechte Seite zu „kippen“.Wir wollen in Python eine Funktion schreiben, die eine Matrix nimmt und einmal nach rechts rotiert.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 Dienstprogrammfunktion zum Drucken einer Matrix. 

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

Eine Methode zum Drehen einer Matrix besteht darin, dies Schicht für Schicht zu tun.Aber was ist eine Schicht?Denken Sie an eine Zwiebel.Genau wie bei den Schichten einer Zwiebel bewegen wir uns beim Entfernen jeder Schicht zur Mitte hin.Andere Analogien sind a Matroschka-Puppe oder eine Partie Pass-the-Parcel.

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

Eine 2×2-Matrix hat 1 Schicht

. .
. .

Eine 3×3-Matrix besteht aus 2 Schichten

. . .
. x .
. . .

Eine 4×4-Matrix besteht aus 2 Schichten

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

Eine 5×5-Matrix besteht aus 3 Schichten

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

Eine 6×6-Matrix besteht aus 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 zu einer Erhöhung der Anzahl der Ebenen führt.Wenn wir die obigen Matrizen betrachten und die Schichten und Abmessungen tabellarisch darstellen, sehen wir, dass die Anzahl der Schichten 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 |
+-----+--------+

Allerdings müssen nicht alle Schichten gedreht werden.Eine 1×1-Matrix ist vor und nach der Rotation gleich.Die zentrale 1×1-Schicht ist vor und nach der Rotation 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 bei einer gegebenen 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 Entspricht die Anzahl der Ebenen, die gedreht werden müssen?Manchmal ist die Anzahl der drehbaren Schichten eins weniger als die Gesamtzahl der Schichten in der Matrix.Dies geschieht, wenn die innerste Schicht nur aus einem Element besteht (d. h.eine 1×1-Matrix) und muss daher nicht gedreht werden.Es wird einfach ignoriert.

Wir werden diese Informationen zweifellos in unserer Funktion zum Drehen einer Matrix benötigen, also 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 zunächst die Spalten an.Die Position der Spalten, die die äußerste Ebene definieren, sind 0 und 4, wenn wir von 0 aus zählen:

+--------+-----------+
| 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 wird immer der Fall sein, da Breite und Höhe gleich sind.Daher können wir die Spalten- und Zeilenpositionen einer Ebene mit nur zwei Werten (statt vier) definieren.

Wenn wir uns nach innen zur zweiten Ebene bewegen, sind die Positionen der Spalten 1 und 3.Und ja, Sie haben es erraten, das gilt auch für Zeilen.Es ist wichtig zu verstehen, dass wir beim Übergang zur nächsten Ebene die Zeilen- und Spaltenpositionen sowohl erhöhen als auch verringern mussten.

+-----------+---------+---------+---------+
|   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, benötigen wir eine Schleife mit steigenden und fallenden Zählern, die die Bewegung nach innen darstellen, beginnend mit der äußersten Ebene.Wir nennen dies unsere „Ebenenschleife“. 

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 (Zeilen- und Spalten-)Positionen 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 bereitstellt.Die Variablen first Und last Identifizieren Sie 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 Schichten 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. Versuchen Sie daher bitte, ihn zu verstehen, bevor Sie fortfahren.

Jetzt brauchen wir eine Möglichkeit, Elemente tatsächlich zu bewegen, d.h.Drehen Sie jedes Element und anschließend die Ebene und schließlich die Matrix.Der Einfachheit halber greifen wir auf eine 3x3-Matrix zurück, die über eine drehbare Ebene verfügt.

0 1 2
3 4 5
6 7 8

Unsere Layer-Schleife stellt die Indizes der ersten und letzten Spalten sowie der ersten und letzten Zeilen bereit:

+-----+-------+
| 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: first Und last, da 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 mithilfe verschiedener Permutationen definiert werden können first Und last (ohne Subtraktion, Addition oder Offset dieser Variablen):

+---------------+-------------------+-------------+
| 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 mit der Drehung an den äußeren vier Ecken – diese drehen wir zuerst.Markieren wir sie mit *.

* 1 *
3 4 5
* 7 *

Wir wollen jeden tauschen * mit dem * rechts davon.Lassen Sie uns also unsere Ecken ausdrucken, die nur durch verschiedene Permutationen von definiert wurden first Und 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önnten wir ganz einfach jede Ecke innerhalb unserer Ebenenschleife austauschen:

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 der Ecken:

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

Matrix nach dem Drehen der Ecken:

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

Großartig!Wir haben jede Ecke der Matrix erfolgreich gedreht.Allerdings haben wir 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 bisher 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 rotiert werden müssen).Der Funktionscode wurde weggelassen, er 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 bemerken möglicherweise auch, 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 auch um die Ecken jeder Ebene zu drehen.Das fühlt sich wie ein Fortschritt an, aber leider müssen wir einen Schritt zurücktreten.Es nützt einfach nichts, 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.Es reicht nicht, nur die Ecken zu drehen!

Tief durchatmen.Wir brauchen eine weitere Schleife.Nicht weniger eine verschachtelte Schleife.Die neue, verschachtelte Schleife verwendet die first Und last Variablen sowie einen Offset zum Navigieren innerhalb einer Ebene.Wir nennen diese neue Schleife unsere „Elementschleife“.Die Elementschleife besucht jedes Element entlang der oberen Reihe, jedes Element unten auf der rechten Seite, jedes Element entlang der unteren Reihe und jedes Element oben auf der linken Seite.

  • Wenn Sie nach vorne in der oberen Reihe vorwärts gehen, muss der Spaltenindex erhöht werden.
  • Um die rechte Seite nach unten zu bewegen, muss der Zeilenindex erhöht werden.
  • Um sich entlang des Bodens nach unten zu bewegen, muss der Spaltenindex dekrementiert werden.
  • Um die linke Seite nach oben zu bewegen, muss der Reihenindex abgeschlossen werden.

Das hört sich komplex an, ist aber einfach, da die Häufigkeit, mit der wir erhöhen und verringern, um das oben Gesagte zu erreichen, auf allen vier Seiten der Matrix gleich bleibt.Zum Beispiel:

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

Das bedeutet, dass wir eine einzelne Variable in Kombination mit verwenden können first Und last Variablen zum Verschieben innerhalb einer Ebene.Es kann hilfreich sein zu beachten, dass die Bewegung über die obere Reihe und die rechte Seite nach unten jeweils eine Inkrementierung erfordert.Bei der Rückwärtsbewegung entlang der Unterseite und der Aufwärtsbewegung auf der linken Seite ist jeweils eine Dekrementierung erforderlich.

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 zuordnen, die rechte Seite der Unterseite, die Unterseite der linken Seite und die linke Seite der Oberseite.Wenn wir das alles zusammenfassen, 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

Gegeben sei die Matrix:

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

Unser rotate Funktion ergibt: 

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

Python:

rotated = zip(*original[::-1])  # On Python 3, list(zip(*original[::-1]))

Billig, ich weiß.

Und gegen den Uhrzeigersinn:

rotated_ccw = zip(*original)[::-1]  # On Python 3, list(zip(*original))[::-1]

So funktioniert das: (In Kommentaren angefordert)

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

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

Der [::-1] Die Anweisung kehrt Array-Elemente um (siehe Erweiterte Slices).

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

Die Kombination beider ergibt schließlich die Rotationstransformation.

Die Änderung der Platzierung von [::-1] kehrt Listen auf verschiedenen Ebenen der Matrix um.

Hier ist eines, das die Drehung an Ort und Stelle durchführt, anstatt ein völlig neues Array zum Speichern des Ergebnisses zu verwenden.Ich habe auf die Initialisierung des Arrays und den Ausdruck verzichtet.Dies funktioniert nur für quadratische Arrays, diese können jedoch jede beliebige Größe haben.Der Speicheraufwand entspricht der Größe eines Elements des Arrays, sodass Sie ein Array so groß drehen können, wie Sie möchten.

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;
    }
}

Hier gibt es jede Menge guten Code, aber ich möchte nur zeigen, was geometrisch vor sich geht, damit Sie die Codelogik etwas besser verstehen können.So würde ich das angehen.

Verwechseln Sie dies zunächst nicht mit der Transposition, die sehr einfach ist.

Die Grundidee besteht darin, es als Ebenen zu behandeln und eine Ebene nach der anderen zu drehen.

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

Lassen Sie uns dies also zerlegen. Zuerst drehen wir im Wesentlichen die 4 Ecken

1           4


13          16

Dann drehen wir den folgenden Diamanten, der irgendwie schief steht

    2
            8
9       
        15

und dann der 2. schräge Diamant

        3
5           
            12
    14

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

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

6   7
10  11

Lassen Sie uns nun die Indizes jeder Ebene ermitteln. Gehen wir davon aus, dass wir immer mit der äußersten Ebene arbeiten

[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]

Also weiter und so weiter, bis wir die Hälfte durch die Kante sind

also im Allgemeinen ist 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 jede Matrixgröße implementiert.Der Kürze und Lesbarkeit halber gibt es keine Fehlerprüfung 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 hebe meine Hand, es werden beim Drehen eigentlich keine Änderungen am ursprünglichen Array vorgenommen.Aber in einem OO-System spielt das keine Rolle, solange das Objekt so aussieht, als wäre es zu den Clients der Klasse rotiert worden.Im Moment verwendet die Matrix-Klasse Verweise auf die ursprünglichen Array-Daten, sodass eine Änderung eines beliebigen Werts von m1 auch eine Änderung von m2 und m3 zur Folge hat.Eine kleine Änderung am Konstruktor, um ein neues Array zu erstellen und die Werte dorthin zu kopieren, wird das klären.

Während es notwendig sein kann, die Daten vor Ort zu rotieren (vielleicht um die physisch gespeicherte Darstellung zu aktualisieren), wird es einfacher und möglicherweise leistungsfähiger, dem Array-Zugriff eine Indirektionsebene hinzuzufügen, vielleicht eine Schnittstelle:

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

Wenn dein Matrix implementiert diese Schnittstelle bereits, dann kann sie über a gedreht werden Dekorateur Klasse so:

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);
    }
}

Auch das Drehen um +90/-90/180 Grad, das horizontale/vertikale Spiegeln und die Skalierung können auf diese Weise erreicht werden.

Die Leistung müsste in Ihrem spezifischen Szenario gemessen werden.Allerdings wurde die O(n^2)-Operation jetzt durch einen O(1)-Aufruf ersetzt.Es ist ein virtueller Methodenaufruf, der Ist langsamer als der direkte Array-Zugriff, daher hängt es davon ab, wie oft das gedrehte Array nach der Rotation verwendet wird.Wenn es einmal verwendet wird, würde dieser Ansatz definitiv gewinnen.Wenn es rotiert und dann tagelang in einem System mit langer Laufzeit verwendet wird, kann die In-Place-Rotation möglicherweise eine bessere Leistung erbringen.Es kommt auch darauf an, ob Sie die Vorabkosten akzeptieren können.

Wie bei allen Leistungsproblemen gilt: 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 der Drehung
  • w ist hier die Breite der Matrix nach der Drehung

 

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.

Ruby-Weg: .transpose.map &:reverse

Es gibt bereits viele Antworten, und ich habe zwei gefunden, die eine zeitliche Komplexität von O(1) beanspruchen.Der real Der O(1)-Algorithmus besteht darin, den Array-Speicher unberührt zu lassen und die Art und Weise zu ändern, wie Sie seine Elemente indizieren.Das Ziel hierbei ist, dass weder zusätzlicher Speicher verbraucht noch zusätzliche Zeit für die Iteration der Daten benötigt wird.

Drehungen um 90, -90 und 180 Grad sind einfache Transformationen, die durchgeführt werden können, solange Sie wissen, wie viele Zeilen und Spalten Ihr 2D-Array enthält;Um einen beliebigen Vektor um 90 Grad zu drehen, vertauschen Sie die Achsen und negieren Sie die Y-Achse.Vertauschen Sie für -90 Grad die Achsen und negieren Sie die X-Achse.Für 180 Grad negieren Sie beide Achsen, ohne sie zu vertauschen.

Weitere Transformationen sind möglich, wie zum Beispiel horizontale und/oder vertikale Spiegelung durch unabhängige Negation der Achsen.

Dies kann z.B. erfolgen.eine Zugriffsmethode.Bei den folgenden Beispielen handelt es sich um JavaScript-Funktionen, die Konzepte gelten jedoch gleichermaßen für alle Sprachen.

 // 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 geht von einem Array aus verschachtelten Arrays aus, 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 nun einfach die richtige aufzurufende Funktion aus, wahrscheinlich per Referenz, und schon kann es losgehen!

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

Einige Leute haben bereits Beispiele bereitgestellt, bei denen es um die Erstellung eines neuen Arrays geht.

Ein paar andere Dinge, die Sie beachten sollten:

(a) Anstatt die Daten tatsächlich zu verschieben, durchlaufen Sie einfach das „gedrehte“ Array auf andere Weise.

(b) Die Rotation vor Ort durchzuführen kann etwas schwieriger sein.Sie benötigen etwas Freiraum (wahrscheinlich ungefähr so ​​groß wie eine Zeile oder Spalte).Es gibt einen alten ACM-Artikel über die Durchführung von In-Place-Transponierungen (http://doi.acm.org/10.1145/355719.355729), aber ihr Beispielcode ist fieses, mit Goto-Elementen beladenes FORTRAN.

Nachtrag:

http://doi.acm.org/10.1145/355611.355612 ist ein weiterer, angeblich überlegener In-Place-Transponierungsalgorithmus.

Nicks Die Antwort würde mit nur einer kleinen Änderung auch für ein NxM-Array 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, sich das vorzustellen, besteht darin, dass Sie den Mittelpunkt der Achse (0,0) von der oberen linken Ecke in die obere rechte Ecke verschoben haben.Sie übertragen 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 aber trotzdem wie beschrieben dreht).

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 Quadrate.Für ein nicht quadratisches 2D-Array 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.jede Zeile transponieren und dann 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 tun 3 einfache Schritte:

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)Zeilen vertauschen, 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

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);
    }
}
?>

Dies ist meine Implementierung in C, O(1)-Speicherkomplexität, Ortsdrehung, 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 zunächst die äußerste Schicht gedreht und dann schrittweise zur inneren Schicht bewegt.

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 nun eine A-Transponierung

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

Und betrachten Sie die Wirkung von A' auf B oder B auf A'.
Jeweils:

      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 n x n-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

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 Array-Klasse von Ruby, also:

% 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 es hier sehen:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transposeindem Sie neben „Transponieren“ die Option „Zum Umschalten der Quelle klicken“ wählen.

Ich erinnere mich besser als an O(n^2)-Lösungen, aber nur für speziell konstruierte Matrizen (z. B. dünn besetzte 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 Matrixdrehung um 90 Grad, eine zweistufige Lösung in C.Transponieren Sie zunächst 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;
}

@dagorym:Oh Mann.Ich hatte daran festgehalten, dass es sich um ein gutes „Mir ist langweilig, worüber kann ich nachdenken?“-Rätsel handelte.Ich habe mir meinen In-Place-Transpositionscode ausgedacht, aber als ich hierher kam, stellte ich fest, dass Ihr ziemlich identisch mit meinem war ... 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 entstehen würde.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top