Jak obrócić tablicę dwuwymiarową?

302

Zainspirowany postem Raymonda Chena , powiedz, że masz dwuwymiarową tablicę 4x4, napisz funkcję, która obraca ją o 90 stopni. Raymond prowadzi do rozwiązania w pseudo-kodzie, ale chciałbym zobaczyć kilka rzeczy z prawdziwego świata.

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

Staje się:

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

Aktualizacja : odpowiedź Nicka jest najprostsza, ale czy istnieje sposób, aby to zrobić lepiej niż n ^ 2? Co jeśli matryca miała wymiary 10000 x 10000?

swilliams
źródło
99
Jak możesz uciec z mniej niż n ^ 2? Wszystkie elementy muszą zostać odczytane i ustawione, a elementów jest n ^ 2
erikkallen
9
Jakie jest twoje n? Nie mówisz, czy tablica 2D jest kwadratowa (nie jest tak w ogólnym przypadku! Np. Wektor jest macierzą o jednym wymiarze 1), ale wydaje się, że sugerujesz, że n jest szerokością i wysokością, a zatem mają elementy n² . Bardziej sensowne byłoby mieć n jako liczbę elementów, gdzie n = w × h.
niXar
1
Oto szybki sposób: przechowywanie indeksów wierszy i kolumn (powiedzmy i i j). Transpozycja trwa cały czas (wystarczy zamienić wskaźniki :). Możesz zrobić to samo z obrotami (grać indeksami).
saadtaame
4
W przypadku, gdy n ^ 2 nie jest wykonalne. Możesz stworzyć interfejs, który ma dostęp do każdego elementu. Następnie podano (i, j), zastosuj obrót, aby (i, j) uzyskać dostęp do obracanego elementu i powrócić. Może nie być najlepszym rozwiązaniem, ale działa.
Confuse

Odpowiedzi:

140

Tutaj jest w 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;
}
Nick Berardi
źródło
6
Jasne, ale co z rozwiązaniem wykorzystującym pamięć O (1)?
AlexeyMK,
20
Twoje rozwiązanie ma złożoność przestrzenną O (n ^ 2). Trzeba zrobić lepiej
Kshitij Jain
6
Co powiesz na macierz NXM?
Rohit,
17
Złożoność jest liniowa pod względem liczby elementów w tablicy. Jeśli N jest liczbą elementów, złożoność wynosi O (N). Jeśli N jest długością boku, to tak, złożoność wynosi O (N ^ 2), ale nadal jest optymalna. Musisz przeczytać każdy element przynajmniej raz. Drukowanie matrycy to ta sama złożoność
Alejandro
6
Dla obrotu o -90 stopni:ret[i][j] = matrix[j][n - i - 1]
Duncan Luk
387

Czas O (n ^ 2) i algorytm przestrzenny O (1) (bez żadnych obejść i cholernie dziwnych rzeczy!)

Obróć o +90:

  1. Transponować
  2. Odwróć każdy rząd

Obróć o -90:

Metoda 1:

  1. Transponować
  2. Odwróć każdą kolumnę

Metoda 2:

  1. Odwróć każdy rząd
  2. Transponować

Obróć o +180:

Metoda 1 : Obróć dwukrotnie o +90

Metoda 2 : Odwróć każdy wiersz, a następnie odwróć każdą kolumnę (transponuj)

Obróć o -180:

Metoda 1 : Obróć dwukrotnie o -90

Metoda 2 : Odwróć każdą kolumnę, a następnie odwróć każdy wiersz

Metoda 3 : Obróć o +180, ponieważ są one takie same

85%
źródło
4
To było dla mnie bardzo pomocne; Byłem w stanie napisać algorytm, kiedy poznałem „[pseudo-] wersję kodu” tej operacji. Dzięki!
duma,
13
Jedna z moich ulubionych SO odpowiedzi wszechczasów. Bardzo pouczające!
g33kz0r
2
Oto implementacja JavaScript JSFiddle, jeśli ktoś jest zainteresowany.
Pan Polywhirl
6
Obróć o -90: (1) Odwróć każdy rząd; (2) Transpozycja. Haskell: rotateCW = map reverse . transposeirotateCCW = transpose . map reverse
Thomas Eding
5
Jaka jest różnica między obrotem o 180 a -180?
Qian Chen
177

Chciałbym dodać trochę więcej szczegółów. W tej odpowiedzi kluczowe pojęcia są powtarzane, tempo jest powolne i celowo powtarzalne. Przedstawione tutaj rozwiązanie nie jest najbardziej kompaktowe pod względem składniowym, jest jednak przeznaczone dla tych, którzy chcą dowiedzieć się, czym jest rotacja macierzy i wynikająca z niej implementacja.

Po pierwsze, czym jest matryca? Na potrzeby tej odpowiedzi macierz jest po prostu siatką, w której szerokość i wysokość są takie same. Uwaga: szerokość i wysokość matrycy mogą być różne, ale dla uproszczenia w tym samouczku uwzględniono tylko matryce o równej szerokości i wysokości ( matryce kwadratowe ). I tak, macierze to liczba mnoga macierzy.

Przykładowe macierze to: 2 × 2, 3 × 3 lub 5 × 5. Lub, bardziej ogólnie, N × N. Matryca 2 × 2 będzie miała 4 kwadraty, ponieważ 2 × 2 = 4. Matryca 5 × 5 będzie miała 25 kwadratów, ponieważ 5 × 5 = 25. Każdy kwadrat nazywa się elementem lub wpisem. Będziemy reprezentować każdy element kropką ( .) na poniższych schematach:

Matryca 2 × 2

. .
. .

Matryca 3 × 3

. . .
. . .
. . .

Matryca 4 × 4

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

Co to znaczy obrócić matrycę? Weźmy macierz 2 × 2 i umieśćmy liczby w każdym elemencie, aby można było zaobserwować obrót:

0 1
2 3

Obracanie o 90 stopni daje nam:

2 0
3 1

Dosłownie raz obróciliśmy całą matrycę w prawo, podobnie jak obracanie kierownicy samochodu. Pomóc może „przewrócenie” matrycy na jej prawą stronę. Chcemy napisać w Pythonie funkcję, która pobiera macierz i obraca się raz w prawo. Podpis funkcji będzie:

def rotate(matrix):
    # Algorithm goes here.

Macierz zostanie zdefiniowana za pomocą dwuwymiarowej tablicy:

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

Dlatego pierwsza pozycja indeksu uzyskuje dostęp do wiersza. Druga pozycja indeksu uzyskuje dostęp do kolumny:

matrix[row][column]

Zdefiniujemy funkcję narzędziową do drukowania matrycy.

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

Jedną z metod obracania matrycy jest robienie z niej warstwy na raz. Ale czym jest warstwa? Pomyśl o cebuli. Podobnie jak warstwy cebuli, gdy każda warstwa jest usuwana, przesuwamy się w kierunku środka. Inne analogie to lalka Matryoshka lub gra pass-the-parcel.

Szerokość i wysokość matrycy decydują o liczbie warstw w tej macierzy. Użyjmy różnych symboli dla każdej warstwy:

Matryca 2 × 2 ma 1 warstwę

. .
. .

Matryca 3 × 3 ma 2 warstwy

. . .
. x .
. . .

Matryca 4 × 4 ma 2 warstwy

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

Matryca 5 x 5 ma 3 warstwy

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

Matryca 6 × 6 ma 3 warstwy

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

Matryca 7 × 7 ma 4 warstwy

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

Można zauważyć, że zwiększenie szerokości i wysokości matrycy o jeden nie zawsze zwiększa liczbę warstw. Biorąc powyższe macierze i zestawiając warstwy i wymiary, widzimy, że liczba warstw wzrasta raz na każde dwa przyrosty szerokości i wysokości:

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

Jednak nie wszystkie warstwy wymagają obracania. Macierz 1 × 1 jest taka sama przed i po obrocie. Centralna warstwa 1 × 1 jest zawsze taka sama przed i po obrocie, bez względu na to, jak duża jest ogólna matryca:

+-----+--------+------------------+
| 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 |
+-----+--------+------------------+

Biorąc pod uwagę macierz N × N, w jaki sposób możemy programowo określić liczbę warstw, które musimy obrócić? Jeśli podzielimy szerokość lub wysokość przez dwa i zignorujemy resztę, otrzymamy następujące wyniki.

+-----+--------+------------------+---------+
| 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 |
+-----+--------+------------------+---------+

Zauważ jak N/2 pasuje liczba warstw, które należy obrócić? Czasami liczba warstw obrotowych jest o jeden mniejsza od całkowitej liczby warstw w matrycy. Dzieje się tak, gdy najbardziej wewnętrzna warstwa jest utworzona tylko z jednego elementu (tj. Matrycy 1 × 1) i dlatego nie musi być obracana. Po prostu zostaje zignorowany.

Niewątpliwie będziemy potrzebować tych informacji w naszej funkcji, aby obrócić macierz, więc dodajmy ją teraz:

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

Teraz wiemy, jakie są warstwy i jak określić liczbę warstw, które faktycznie wymagają obrotu, w jaki sposób izolujemy pojedynczą warstwę, abyśmy mogli ją obrócić? Po pierwsze, sprawdzamy matrycę od zewnętrznej warstwy, do wewnątrz, do wewnętrznej warstwy. Matryca 5 × 5 ma łącznie trzy warstwy i dwie warstwy, które wymagają obrotu:

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

Najpierw spójrzmy na kolumny. Położenie kolumn określających zewnętrzną warstwę, przy założeniu, że liczymy od 0, to 0 i 4:

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

0 i 4 to także pozycje rzędów dla najbardziej zewnętrznej warstwy.

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

Tak będzie zawsze, ponieważ szerokość i wysokość są takie same. Dlatego możemy zdefiniować pozycje kolumny i wiersza warstwy za pomocą tylko dwóch wartości (zamiast czterech).

Przechodząc do drugiej warstwy, pozycje kolumn wynoszą 1 i 3. I tak, zgadliście, to samo dla rzędów. Ważne jest, aby zrozumieć, że musieliśmy zarówno zwiększać, jak i zmniejszać pozycje wierszy i kolumn podczas przechodzenia do wewnątrz do następnej warstwy.

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

Tak więc, aby sprawdzić każdą warstwę, chcemy pętli z licznikami rosnącymi i malejącymi, które reprezentują ruch do wewnątrz, zaczynając od najbardziej zewnętrznej warstwy. Nazwiemy to naszą „pętlą warstw”.

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)

Powyższy kod zapętla pozycje (wierszy i kolumn) dowolnych warstw, które wymagają obrócenia.

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

Mamy teraz pętlę zapewniającą pozycje wierszy i kolumn każdej warstwy. Zmienne firsti lastidentyfikują pozycję indeksu pierwszego i ostatniego wiersza i kolumny. Wracając do naszych tabel wierszy i kolumn:

+--------+-----------+
| 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 | . . . . . |
+-----+-----------+

Możemy więc poruszać się po warstwach matrycy. Teraz potrzebujemy sposobu poruszania się po warstwie, abyśmy mogli przenosić elementy wokół tej warstwy. Uwaga: elementy nigdy nie „przeskakują” z jednej warstwy na drugą, ale poruszają się w obrębie odpowiednich warstw.

Obracanie każdego elementu w warstwie powoduje obrót całej warstwy. Obracanie wszystkich warstw w matrycy powoduje obrót całej matrycy. To zdanie jest bardzo ważne, więc staraj się jak najlepiej je zrozumieć, zanim przejdziesz dalej.

Teraz potrzebujemy sposobu faktycznego przemieszczania elementów, tj. Obracania każdego elementu, a następnie warstwy, a ostatecznie macierzy. Dla uproszczenia powrócimy do matrycy 3x3 - która ma jedną obrotową warstwę.

0 1 2
3 4 5
6 7 8

Nasza pętla warstw zawiera indeksy pierwszej i ostatniej kolumny, a także pierwszego i ostatniego wiersza:

+-----+-------+
| 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 |
+-----+-------+

Ponieważ nasze macierze są zawsze kwadratowe, potrzebujemy tylko dwóch zmiennych, firsta lastponieważ pozycje indeksu są takie same dla wierszy i kolumn.

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.

Zmienne pierwsza i ostatnia mogą być łatwo wykorzystane do odniesienia do czterech rogów macierzy. Wynika to z faktu, że same rogi można zdefiniować za pomocą różnych kombinacji firsti last(bez odejmowania, dodawania lub przesunięcia tych zmiennych):

+---------------+-------------------+-------------+
| 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)       |
+---------------+-------------------+-------------+

Z tego powodu rozpoczynamy obrót w czterech zewnętrznych rogach - najpierw je obrócimy. Wyróżnijmy je za pomocą *.

* 1 *
3 4 5
* 7 *

Chcemy zamienić każdy *z *prawej strony. A więc przejdźmy do wydruku naszych narożników zdefiniowanych przy użyciu tylko różnych kombinacji firsti 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)

Dane wyjściowe powinny wynosić:

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

Teraz możemy dość łatwo zamienić każdy z rogów z naszej pętli warstw:

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)

Matryca przed obracaniem narożników:

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

Matryca po obróceniu narożników:

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

Świetny! Z powodzeniem obróciliśmy każdy narożnik matrycy. Ale nie obróciliśmy elementów na środku każdej warstwy. Oczywiście potrzebujemy sposobu iteracji w obrębie warstwy.

Problem polega na tym, że jedyna jak dotąd pętla w naszej funkcji (nasza pętla warstw) przesuwa się do następnej warstwy przy każdej iteracji. Ponieważ nasza matryca ma tylko jedną warstwę obrotową, pętla warstwy wychodzi po obróceniu tylko narożników. Spójrzmy na to, co dzieje się z większą matrycą 5 × 5 (gdzie dwie warstwy wymagają obrotu). Kod funkcji został pominięty, ale pozostaje taki sam jak powyżej:

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)

Dane wyjściowe to:

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

Nie powinno być zaskoczeniem, że rogi zewnętrznej warstwy zostały obrócone, ale można również zauważyć, że rogi kolejnej warstwy (do wewnątrz) również zostały obrócone. To ma sens. Napisaliśmy kod do poruszania się po warstwach, a także do obracania rogów każdej warstwy. To wydaje się postępem, ale niestety musimy cofnąć się o krok. Po prostu przejście do następnej warstwy nie jest dobre, dopóki poprzednia (zewnętrzna) warstwa nie zostanie całkowicie obrócona. To znaczy, dopóki każdy element w warstwie nie zostanie obrócony. Obracanie tylko narożników nie zadziała!

Weź głęboki oddech. Potrzebujemy kolejnej pętli. Zagnieżdżona pętla nie mniej. Nowe zagnieżdżonej pętli użyje firsti lastzmienne, a także przesunięcie poruszać się w warstwie. Tę nową pętlę nazwiemy „pętlą elementów”. Pętla elementów odwiedzi każdy element wzdłuż górnego rzędu, każdy element po prawej stronie, każdy element wzdłuż dolnego rzędu i każdy element po lewej stronie.

  • Przesunięcie do przodu wzdłuż górnego wiersza wymaga zwiększenia indeksu kolumny.
  • Przesunięcie w dół po prawej stronie wymaga zwiększenia indeksu wierszy.
  • Przesunięcie do tyłu wzdłuż dołu wymaga zmniejszenia indeksu kolumny.
  • Przesunięcie w górę po lewej stronie wymaga zmniejszenia indeksu wiersza.

Brzmi to skomplikowanie, ale jest to łatwe, ponieważ liczba inkrementacji i dekrementacji w celu osiągnięcia powyższego pozostaje taka sama na wszystkich czterech bokach matrycy. Na przykład:

  • Przenieś 1 element w górnym rzędzie.
  • Przesuń 1 element w dół po prawej stronie.
  • Przesuń 1 element do tyłu wzdłuż dolnego rzędu.
  • Przesuń 1 element w górę po lewej stronie.

Oznacza to, że możemy użyć pojedynczej zmiennej w połączeniu ze zmiennymi firsti last, aby poruszać się w warstwie. Warto zauważyć, że poruszanie się w górnym rzędzie i w dół po prawej stronie wymaga zwiększania. Podczas przesuwania się do tyłu wzdłuż dołu i do góry po lewej stronie oba wymagają zmniejszenia.

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)

Teraz musimy po prostu przypisać górę do prawej strony, prawej strony do dołu, od dołu do lewej strony i lewej strony do góry. Łącząc to wszystko, otrzymujemy:

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

Biorąc pod uwagę matrycę:

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

Nasza rotatefunkcja powoduje:

6,  3,  0  
7,  4,  1  
8,  5,  2  
Jack
źródło
Początkowo czułem się jak „wow, najlepsze wyjaśnienie w historii”, ale po przeczytaniu go kilka razy (aby upewnić się, że nie umknęło mi nic ważnego w morzu słów), moje zdanie zmieniło się na „człowiek, rozumiem, mogę poruszamy się, proszę? Nadal głosowałem za poświęcenie kilku godzin na skomponowanie tak skomplikowanej odpowiedzi.
Abhijit Sarkar
1
@AbhijitSarkar - Dzięki za głosowanie i mam nadzieję, że przynajmniej pomogło to w jakiś niewielki sposób. Oczywiście masz rację, moja odpowiedź jest trudna. Było to jednak celowo sprzeczne z ogromną większością odpowiedzi. Jak powiedziałem na samym początku mojej odpowiedzi: „W tej odpowiedzi kluczowe pojęcia są powtarzane, tempo jest powolne i celowo powtarzalne”. Jeśli masz zmiany, które zachowują jasność i niezbędną powtarzalność, ale zmniejszają liczbę słów, jestem bardzo otwarty na sugestie. Lub po prostu edytuj :)
Jack
@jack Naprawdę dobre wyjaśnienie. Nie mogłem jednak nie zrozumieć, jak wymyśliłeś offset = element - pierwszy i ostatni = rozmiar - pierwszy - 1? Czy trudno ci to zrozumieć? Czy ostatnie przesunięcie jest takie samo jak przesunięcie?
ashishjmeshram
1
TL; DR:list(zip(*reversed(your_list_of_lists)))
Boris
127

Pyton:

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

i przeciwnie do ruchu wskazówek zegara:

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

Jak to działa:

zip(*original)zamieni osie tablic 2d układając odpowiednie elementy z list w nowe listy. ( *Operator mówi funkcji, aby podzieliła zawarte listy na argumenty)

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

Te [::-1]elementy rachunku odwraca array (patrz Rozszerzony plastry czy to pytanie ):

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

Wreszcie połączenie tych dwóch elementów spowoduje transformację obrotu.

Zmiana umieszczenia [::-1]spowoduje odwrócenie list na różnych poziomach matrycy.

bcdan
źródło
3
Uważam, że ten kod pochodzi od Petera Norviga
Josip
Możesz użyć zip(*reversed(original))zamiast, zip(*original[::-1])aby uniknąć tworzenia dodatkowej kopii oryginalnej listy.
Boris
70

Oto taki, który wykonuje obrót w miejscu zamiast używać całkowicie nowej tablicy do przechowywania wyniku. Zrezygnowałem z inicjalizacji tablicy i wydrukowałem ją. Działa to tylko dla tablic kwadratowych, ale mogą mieć dowolny rozmiar. Narzut pamięci jest równy rozmiarowi jednego elementu tablicy, dzięki czemu można wykonać obrót tak dużej tablicy, jak chcesz.

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;
    }
}
dagorym
źródło
Widzę co najmniej jeden błąd. Jeśli masz zamiar wysłać kod pocztowy, przetestuj go lub przynajmniej powiedz, że tego nie zrobiłeś.
Hugh Allen
1
Gdzie? Wskaż to, a naprawię to. Testowałem to i działało dobrze zarówno na tablicach nieparzystych, jak i parzystych.
dagorym
2
to piękne rozwiązanie. Umysł może dokonać takich wyczynów, jeśli jest ustawiony na cel. od O (n2) do O (1)
MoveFast
2
To nie jest O (1); wciąż jest O (n ^ 2)
duma
11
Jego O (n ^ 2) z pamięcią O (1).
Neel
38

Jest tu mnóstwo dobrego kodu, ale chcę tylko pokazać, co się dzieje geometrycznie, aby lepiej zrozumieć logikę kodu. Oto jak do tego podejdę.

po pierwsze, nie należy tego mylić z transpozycją, która jest bardzo łatwa ..

podstawową ideą jest traktowanie jej jak warstw i obracamy jedną warstwę naraz.

powiedzmy, że mamy 4x4

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

po obróceniu go o 90 zgodnie z ruchem wskazówek zegara otrzymujemy

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

więc rozłóżmy to, najpierw obrócimy zasadniczo 4 rogi

1           4


13          16

następnie obracamy następujący diament, który jest trochę krzywo

    2
            8
9       
        15

a następnie drugi przekrzywiony diament

        3
5           
            12
    14

tak, że dba o zewnętrzną krawędź, więc zasadniczo wykonujemy tę powłokę na raz

w końcu środkowy kwadrat (lub jeśli jest dziwny tylko ostatni element, który się nie porusza)

6   7
10  11

więc teraz zastanówmy się nad wskaźnikami każdej warstwy, załóżmy, że zawsze pracujemy z najbardziej zewnętrzną warstwą

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

i tak dalej, aż do połowy krawędzi

więc ogólnie wzór jest

[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]
poprawianie
źródło
co to znaczy „w połowie krawędzi”? Widzę wiele algorytmów zapętlających się do N / 2 i innych zapętlających się do N, ale nie widzę, skąd N / 2 pochodzi.
PDN,
Uważam, że to samo rozwiązanie, co w przypadku złamania wywiadu z programistą. Ale podoba mi się wyjaśnienie krok po kroku. Bardzo miły i dokładny.
Naphstor,
@PDN Ta odpowiedź wyjaśnia to szczegółowo.
Mathias Bynens,
35

Jak powiedziałem w poprzednim poście, oto kod w języku C #, który implementuje obrót macierzy O (1) dla macierzy dowolnego rozmiaru. Dla zwięzłości i czytelności nie ma sprawdzania błędów ani sprawdzania zasięgu. Kod:

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, podniosę rękę, tak naprawdę nie robi żadnych modyfikacji oryginalnej tablicy podczas obracania. Ale w systemie OO nie ma znaczenia, dopóki obiekt wygląda, jakby został obrócony do klientów klasy. W tej chwili klasa Matrix używa odniesień do oryginalnych danych macierzy, więc zmiana dowolnej wartości m1 spowoduje również zmianę m2 i m3. Niewielka zmiana w konstruktorze, aby utworzyć nową tablicę i skopiować do niej wartości, rozwiąże ten problem.

Skizz
źródło
4
Brawo! To bardzo miłe rozwiązanie i nie wiem, dlaczego nie jest to akceptowana odpowiedź.
martinatime
@martinatime: być może dlatego, że jest 5 razy większy
Toad
@Toad: Cóż, pisanie kodu jest zawsze kompromis pomiędzy konkurującymi ze sobą wymagania: szybkość, wielkość kosztów, itd.
Skizz
15
prawda… innym problemem jest fakt, że matryca nie jest faktycznie obracana, ale obracana „w samą porę”. Co jest świetne do uzyskiwania dostępu do kilku elementów, ale byłoby okropne, gdyby ta matryca była używana w obliczeniach lub manipulacjach obrazem. Zatem powiedzenie O (1) nie jest tak naprawdę uczciwe.
Ropucha
23

Podczas gdy obracanie danych w miejscu może być konieczne (być może w celu zaktualizowania fizycznie przechowywanej reprezentacji), staje się łatwiejsze i być może bardziej wydajne, aby dodać warstwę pośrednią do dostępu do tablicy, być może interfejs:

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

Jeśli Matrixjuż implementujesz ten interfejs, możesz go obrócić za pomocą klasy dekoratora, takiej jak ta:

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

Obracanie o + 90 / -90 / 180 stopni, obracanie w poziomie / w pionie i skalowanie można również osiągnąć w ten sposób.

Wydajność musiałaby być mierzona w konkretnym scenariuszu. Jednak operacja O (n ^ 2) została teraz zastąpiona wywołaniem O (1). Jest to wirtualne wywołanie metody, które jest wolniejsze niż bezpośredni dostęp do tablicy, więc zależy od tego, jak często obrócona tablica jest używana po rotacji. Jeśli zastosuje się go raz, to podejście na pewno by wygrało. Jeśli jest obrócony, a następnie używany przez długi czas w systemie, rotacja w miejscu może działać lepiej. Zależy to również od tego, czy możesz zaakceptować koszty początkowe.

Podobnie jak w przypadku wszystkich problemów z wydajnością, mierz, mierz, mierz!

Drew Noakes
źródło
1
+1 ... A jeśli matryca jest naprawdę duża i masz dostęp tylko do kilku elementów (rzadkie użycie), jest to jeszcze bardziej skuteczne
lothar
16
Trochę niesprawiedliwe jest nazywanie tego rozwiązaniem czasu O (1). Aby rozwiązać problem związany z OP, nadal zajmie to czas O (n ^ 2). Co więcej, nie rozwiązałoby problemu, ponieważ zwraca transpozycję . Podany przykład nie ma transpozycji jako rozwiązania.
Vlad the Impala,
5
Teraz, jeśli wszystko, czego chciałeś, to pierwsze 3 elementy macierzy, jest to dobre rozwiązanie, ale problemem jest odzyskanie całkowicie transformowanej macierzy (tj. Zakładając, że potrzebujesz wszystkich elementów macierzy). Nazywanie tego O (1) jest metodą analizy domyślnego swapu ryzyka kredytowego - nie rozwiązałeś problemu, po prostu przekazałeś go komuś innemu :)
Ana Betts
4
@Paul Betts: Rozumiem, ale jak napisałem powyżej w komentarzach, nawet jeśli faktycznie macie transponowaną matrycę, nadal musicie napisać pętlę, jeśli chcecie odczytać wartości. Czytanie wszystkich wartości z macierzy zawsze oznacza O (N ^ 2) niezależnie. Różnica polega na tym, że jeśli dokonujesz transpozycji, obracania, skalowania, skalowania ponownie itp., Nadal otrzymujesz trafienie O (N ^ 2) tylko raz. Jak powiedziałem, nie zawsze jest to najlepsze rozwiązanie, ale w wielu przypadkach jest odpowiednie i opłacalne. Wydawało się, że OP szuka magicznego rozwiązania, a jest tak blisko, jak tylko się da.
Drew Noakes
9
Podoba mi się ta odpowiedź, ale chcę coś podkreślić. Drukowanie ozdobnej matrycy (i generalnie wykonywanie innych sekwencyjnych odczytów) może być znacznie wolniejsze niż robienie tego samego z matrycą, która została obrócona w pamięci, i to nie tylko z powodu wirtualnych wywołań metod. W przypadku dużej matrycy znacznie zwiększysz liczbę braków w pamięci podręcznej, czytając „w dół” zamiast „w poprzek”.
Mike Daniels,
18

To lepsza wersja w Javie: Zrobiłem to dla matrycy o innej szerokości i wysokości

  • h jest tutaj wysokością matrycy po obróceniu
  • w oznacza tutaj szerokość matrycy po obróceniu

 

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

Ten kod oparty jest na poście Nicka Berardi.

Martijn Courteaux
źródło
Dzięki. To był najczystszy kod Java tutaj. Pytanie - Jak wymyśliłeś / aś Nick z częścią [w - j - 1]? Patrząc na odpowiedź @tweaking, widzę, jak można to uzyskać poprzez przykłady indukcji / rozwiązywania problemów. Zastanawiam się tylko, czy tak to uzyskano, czy też jest oparte na matematycznej zasadzie dotyczącej Matryc.
Quest Monger,
17

Rubinowy sposób: .transpose.map &:reverse

Nakilon
źródło
1
To jeszcze prostsze: array.reverse.transposeobraca tablicę zgodnie z ruchem wskazówek zegara, podczas gdy array.transpose.reverseobraca ją przeciwnie do ruchu wskazówek zegara. Nie ma takiej potrzeby map.
Giorgi Gzirishvili
13

Jest już wiele odpowiedzi i znalazłem dwie twierdzące, że złożoność czasowa O (1). rzeczywistym O (1) algorytm jest pozostawienie przechowywanie tablicy nietknięte i zmienić sposób wskaźnik jego elementy. Chodzi tutaj o to, aby nie zużywał dodatkowej pamięci ani nie wymagał dodatkowego czasu na iterację danych.

Obracanie o 90, -90 i 180 stopni to proste transformacje, które można wykonać, o ile wiesz, ile wierszy i kolumn znajduje się w tablicy 2D; Aby obrócić dowolny wektor o 90 stopni, zamień osie i neguj oś Y. Dla -90 stopni zamień osie i neguj oś X. Dla 180 stopni neguj obie osie bez zamiany.

Możliwe są dalsze przekształcenia, takie jak odbicie lustrzane w poziomie i / lub w pionie poprzez niezależne negowanie osi.

Można tego dokonać np. Metodą akcesora. Poniższe przykłady to funkcje JavaScript, ale pojęcia dotyczą jednakowo wszystkich języków.

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

Ten kod zakłada tablicę zagnieżdżonych tablic, przy czym każda tablica wewnętrzna jest rzędem.

Ta metoda umożliwia odczytywanie (lub zapisywanie) elementów (nawet w losowej kolejności), tak jakby tablica została obrócona lub przekształcona. Teraz wystarczy wybrać odpowiednią funkcję do wywołania, prawdopodobnie przez odniesienie, i gotowe!

Pojęcie to można rozszerzyć, aby zastosować transformacje w sposób addycyjny (i nieniszczący) za pomocą metod akcesorów. W tym dowolne obroty kątów i skalowanie.

Jason Oster
źródło
Jednak żadne z nich nie zostało obrócone z oryginalnej tablicy. Po pierwsze, wynik końcowy jest po prostu transponowany. Drugi wydaje się, że właśnie przetasowałeś rzędy lub odbił lustrzany w poprzek poziomego środka. Trzeci, odwróciłeś tylko rzędy, a czwarty również został transponowany. Żadne z nich nie zostało „obrócone”.
SM177Y,
Istnieją dwa błędy w dwóch ostatnich przykładach. Trywialny do naprawienia. Wskazałem wyraźnie, że to rozwiązanie nie jest rotacją na miejscu. Jest to funkcja transformacji, dzięki czemu nadaje się do leniwej iteracji.
Jason Oster
Tyle że nie ma rotacji, więc właściwie nie odpowiedziałeś na pytanie OP.
SM177Y,
@ SM177Y Inny edytor dodał niedziałający przykładowy kod do mojej odpowiedzi. Widzę, jak się tym pomyliłeś. Naprawiłem błędy w pętlach iteracji. Podane funkcje faktycznie „obracają” dane w tablicach.
Jason Oster
Ważnym szczegółem jest również to, że przykładowy kod naprawdę zmywa pierwotną odpowiedź, którą podałem, która próbowała zilustrować potęgę transformacji funkcjonalnych nad liniowymi rozwiązaniami złożoności czasoprzestrzennej. Dzięki transformacji funkcjonalnej już iterujesz lub w inny sposób uzyskujesz dostęp do elementów tablicy , więc transformacja jest uważana za „wolną” w sensie stałej złożoności przestrzeni i czasu.
Jason Oster
10

Kilka osób już podało przykłady, które wymagają stworzenia nowej tablicy.

Kilka innych rzeczy do rozważenia:

(a) Zamiast faktycznie przenosić dane, po prostu przejdź w inny sposób do „obróconej” tablicy.

(b) Wykonanie obrotu w miejscu może być nieco trudniejsze. Potrzebujesz trochę miejsca na zarysowania (prawdopodobnie mniej więcej równego rozmiarowi jednego wiersza lub kolumny). Istnieje starożytna praca ACM na temat dokonywania transpozycji w miejscu ( http://doi.acm.org/10.1145/355719.355729 ), ale ich przykładowy kod to paskudny fortuna z ładunkiem.

Uzupełnienie:

http://doi.acm.org/10.1145/355611.355612 to kolejny, podobno lepszy, lokalny algorytm transpozycji.

nsanders
źródło
Zgadzam się z tym. Mieć metodę, która określa translację między danymi źródłowymi a danymi „obróconymi”.
martinatime
8

Odpowiedź Nicka działałaby również na macierz NxM z niewielką modyfikacją (w przeciwieństwie do 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];

Jednym ze sposobów myślenia o tym jest przeniesienie środka osi (0,0) z lewego górnego rogu do prawego górnego rogu. Po prostu transponujesz z jednego na drugi.

Kevin Berridge
źródło
6

Czas - O (N), Spacja - 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;
        }
    }
}
użytkowników2793692
źródło
To nie jest O (1). To jest O (n).
Jason Oster
@JasonOster Uważam, że jest to przestrzeń O (1), ponieważ nie zajmuje ona dodatkowego miejsca.
ffledgling
@ffledgling My error. O (1) złożoność przestrzeni, tak. O (n) złożoność czasu.
Jason Oster
Złożoność przestrzeni to także O (n). Złożoność przestrzeni powinna obejmować przestrzeń o zmiennej wielkości wejściowej. karierycup.com/question?id=14952322
Jason Heo
Jak mogę to zmienić, aby działało w przypadku obrotu przeciwnego do ruchu wskazówek zegara?
MD XF
5

Oto moja wersja Ruby (zauważ, że wartości nie są wyświetlane tak samo, ale wciąż się obraca zgodnie z opisem).

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

Wyjście:

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
Mike Stone
źródło
4

oto metoda rotacji w przestrzeni, według java, tylko dla kwadratu. w przypadku nie kwadratowej tablicy 2d i tak będziesz musiał utworzyć nową tablicę.

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

kod, aby obrócić tablicę 2d dowolnego rozmiaru, tworząc nową tablicę:

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;
}
James Yu
źródło
3

Implementacja pseudokodu +90 dołka (np. Transpozycja, a następnie odwrócenie każdego wiersza) w 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;
}
mhawksey
źródło
3

Możesz to zrobić w 3 prostych krokach :

1 ) Załóżmy, że mamy matrycę

   1 2 3
   4 5 6
   7 8 9

2 ) Weź transpozycję macierzy

   1 4 7
   2 5 8
   3 6 9

3 ) Zamień rzędy, aby uzyskać obróconą matrycę

   3 6 9
   2 5 8
   1 4 7

Kod źródłowy Java dla tego:

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

Wynik:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 
Prateek Joshi
źródło
2

To jest moja implementacja, w złożoności pamięci C, O (1), w miejscu obrotu, 90 stopni w prawo:

#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;
        }
    }
}
Spidey
źródło
2

Oto wersja Java:

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

metoda najpierw obraca najbardziej rutynową warstwę, a następnie przechodzi do warstwy wewnętrznej pośrodku.

rad
źródło
2

Z liniowego punktu widzenia rozważmy macierze:

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

Teraz weź transpozycję A

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

I rozważ działanie A 'na B lub B na A'.
Odpowiednio:

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

Można to rozszerzyć dla dowolnej macierzy nxn. I szybkie zastosowanie tej koncepcji w kodzie:

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);
        }
    }
}
Pan Nex
źródło
2

Kod C # do obracania [n, m] Tablice 2D o 90 stopni w prawo

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

Wynik:

    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
ustmaestro
źródło
2

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

Od PHP 5.6 transpozycja macierzy może być wykonywana za pomocą eleganckiego array_map()wywołania. Innymi słowy, kolumny są konwertowane na wiersze.

Kod: ( Demo )

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

$ transponowane:

[
    [1, 5, 9, 3],
    [2, 6, 0, 4],
    [3, 7, 1, 5],
    [4, 8, 2, 6]
]
James Lin
źródło
1

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

X to rozmiar tablicy, w której znajduje się grafika.

Turek
źródło
1

#transpose jest standardową metodą klasy Ruby's Array, a zatem:

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

Implementacja jest funkcją transpozycji n ^ 2 napisaną w C. Możesz ją zobaczyć tutaj: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose wybierając „kliknij przełączać źródło „obok” transpozycji ”.

Pamiętam rozwiązania lepsze niż O (n ^ 2), ale tylko dla specjalnie skonstruowanych matryc (takich jak matryce rzadkie)

k00ka
źródło
1

Kod C dla obrotu matrycy o 90 stopni w prawo W MIEJSCU dla dowolnej matrycy M * N

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;
        }
    }
}
rohitmb
źródło
1

oto moja implementacja In Place w 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;
        }
    }
}
Thiagoh
źródło
1

Oto moja próba rotacji matrycy o 90 stopni, która jest 2-etapowym rozwiązaniem w C. Najpierw transponuj matrycę na miejsce, a następnie zamień cols.

#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;
}
użytkownik1596193
źródło
1

@dagorym: Aw, stary. Trzymałem się tego jako dobrej łamigłówki „Jestem znudzony, co mogę rozważać”. Wymyśliłem swój lokalny kod transpozycji, ale dotarłem tutaj, by znaleźć twój prawie identyczny z moim ... och, cóż. Tutaj jest w 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
Nathan Fritz
źródło
1
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];
  }
}

Prosta metoda C ++, ponieważ w dużej tablicy byłby duży narzut pamięci.

William
źródło
Wśród wszystkich tych odpowiedzi znalazłem i przetestowałem tę, która jest kompaktowa i wystarczająca do obracania
dlewin