Rotate Image

Q: Jaka jest złożoność czasowa i pamięciowa obracania macierzy?

Obrócenie macierzy n × n zajmuje czas O(n²), ponieważ niemal każda wartość musi zostać przesunięta. Metoda transpozycji i odwracania wymaga O(1) dodatkowej pamięci. Utworzenie obróconej kopii również zajmuje czas O(n²), ale wymaga O(n²) dodatkowej pamięci.

ŚrednieTablice i napisy Matematyka i symulacja

+10

Otrzymujesz siatkę n × n liczb całkowitych, po jednej liście na każdy wiersz. Obróć ją o ćwierć obrotu zgodnie z ruchem wskazówek zegara i zwróć. Górny wiersz staje się skrajną prawą kolumną, drugi wiersz kolumną po jego lewej stronie i tak dalej: wartość w (i, j) trafia do (j, n-1-i). Możesz zmienić siatkę w miejscu; zwróć ją.

Funkcja

rotateImage(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: kwadratowa siatka, jedna lista wewnętrzna na każdy wiersz
Zwracainteger-2d-array: macierz obrócona o 90 stopni w prawo

Ograniczenia

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Przykłady

Wejście: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Wyjście: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Wyjaśnienie: Pierwszy wiersz, 3 7 1, staje się ostatnią kolumną czytaną od góry do dołu. Pierwsza kolumna, 3 9 4, czytana od dołu do góry, staje się pierwszym wierszem [4, 9, 3]. Środkowa wartość 5 pozostaje na swoim miejscu.

Pytanie dodatkowe

Które dwa kroki wykonywane w miejscu obracają macierz o 180 stopni i czy da się to zrobić w jednym przebiegu zamian?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

To, dokąd trafia każda wartość, określa wzór: (i, j) przechodzi do (j, n-1-i). Trudność polega na przenoszeniu wartości bez użycia drugiej macierzy, ponieważ wpisanie wartości do nowej komórki nadpisuje wartość, która nie została jeszcze przeniesiona. Transpozycja, po której następuje odwrócenie kolejności wierszy, pozwala uzyskać ten sam obrót o ćwierć obrotu za pomocą zamiany par wartości.

Zbuduj obróconą kopię

Intuicja

Wiersz i staje się kolumną n-1-i, a wartość z pozycji j w wierszu trafia na pozycję j w dół tej kolumny, czyli do wiersza j. Zatem result[j][n-1-i] = matrix[i][j]. W pierwszym przykładzie 4 z wiersza 2, kolumny 0 trafia do wiersza 0, kolumny 0, dlatego odpowiedź zaczyna się od 4.

Wartości przemieszczają się w cyklach po cztery, więc zapis w miejscu spowodowałby skasowanie wartości, zanim zdążyłaby się przemieścić: 3 nadpisałoby 1 w prawym górnym rogu. Kopia kosztuje dodatkowe n² komórek, czyli 4,900 dla n = 70.

Algorytm

Utwórz macierz wynikową n × n.
Dla każdego wiersza i i kolumny j skopiuj matrix[i][j] do result[j][n-1-i].
Zwróć wynik.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Transponuj, a następnie odwróć każdy wiersz

Intuicja

Transpozycja przenosi (i, j) do (j, i), a odwrócenie wiersza przenosi kolumnę c do kolumny n-1-c. Razem przenoszą (i, j) do (j, n-1-i), dokładnie tam, gdzie umieszcza je obrót.

Obie operacje wykonują się w miejscu, ponieważ każda składa się z par zamian. W transpozycji matrix[i][j] i matrix[j][i] powinny znaleźć się w komórkach należących do siebie nawzajem, więc jedna zamiana załatwia obie. Zamieniaj tylko pary, dla których j > i, w przeciwnym razie każda para zostanie zamieniona z powrotem. Odwracanie wiersza polega na zamianie jego dwóch końców i przesuwaniu się do środka.

W pierwszym przykładzie transpozycja daje [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: każdy wiersz zawiera teraz dawną kolumnę. Odwrócenie każdego wiersza daje wynik.

Transpozycja wymaga n(n-1)/2 zamian, a odwracanie n·⌊n/2⌋, więc złożoność czasowa wynosi O(n²), a dodatkowa pamięć obejmuje kilka zmiennych. Wersja w R najpierw kopiuje dane wejściowe do macierzy R, więc jej dodatkowa pamięć wynosi O(n²).

Algorytm

Dla każdej komórki powyżej głównej przekątnej, (i, j) z j > i, zamień jej wartość z wartością komórki (j, i).
Dla każdego wiersza zamień miejscami pierwszą i ostatnią wartość, a następnie przesuwaj oba końce do środka, aż się spotkają.
Zwróć macierz.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Pułapki i przypadki brzegowe

Transponowanie z j zaczynającym się od 0. Każda para zostaje zamieniona dwukrotnie, co znosi transpozycję, więc wynikiem jest tylko odwrócenie kolejności wierszy, czyli lustrzane odbicie.
Odwracanie przed transponowaniem. Taka kolejność obraca macierz przeciwnie do ruchu wskazówek zegara. Test na macierzy 2 × 2 to wykryje: [[1, 2], [3, 4]] musi zmienić się w [[3, 1], [4, 2]].
Zapisywanie matrix[j][n-1-i] = matrix[i][j] w tej samej macierzy. Komórka docelowa nadal zawiera wartość, która nie została przeniesiona, i zostaje utracona.
Używanie n-i zamiast n-1-i. Przy indeksach liczonych od 0 ostatnia kolumna ma indeks n-1, więc n-i wykracza poza koniec dla i = 0.

Najczęstsze pytania3

Jaka jest złożoność czasowa i pamięciowa obracania macierzy?

Obrócenie macierzy n × n zajmuje czas O(n²), ponieważ niemal każda wartość musi zostać przesunięta. Metoda transpozycji i odwracania wymaga O(1) dodatkowej pamięci. Utworzenie obróconej kopii również zajmuje czas O(n²), ale wymaga O(n²) dodatkowej pamięci.

Jak obrócić macierz przeciwnie do ruchu wskazówek zegara?

Zamień kolejność tych dwóch kroków: najpierw odwróć każdy wiersz, a następnie wykonaj transpozycję. Możesz też najpierw wykonać transpozycję, a potem odwrócić kolejność wierszy. W obu przypadkach wartość na pozycji (i, j) znajdzie się na pozycji (n-1-j, i).

Czy potrafisz obrócić macierz, przesuwając za każdym razem cztery wartości?

Tak. Każda wartość poza środkiem należy do cyklu czterech komórek: (i, j), (j, n-1-i), (n-1-i, n-1-j) i (n-1-j, i). Pierścień po pierścieniu przechowuj jedną wartość z każdego cyklu w zmiennej i przesuwaj pozostałe trzy. Ma to ten sam czas O(n²) i pamięć O(1), ale więcej działań na indeksach, które można wykonać błędnie.

def rotateImage(matrix):
    # Wpisz kod tutaj

Test #1

Test #2

Argument

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

Oczekiwany wynik

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