Transpose Matrix

Q: Jaka jest złożoność czasowa transponowania macierzy?

O(m × n) : każda z m × n wartości jest kopiowana raz i nic mniej nie pozwoli uzyskać odpowiedzi. Nowa macierz zajmuje O(m × n) pamięci, tyle, ile wynosi rozmiar samego wyniku.

Q: Czy możesz transponować macierz w miejscu?

W przypadku macierzy kwadratowej tak: zamień miejscami matrix[i][j] i matrix[j][i] dla każdej komórki powyżej przekątnej, używając dodatkowo O(1) pamięci. Macierz niekwadratowa zmienia kształt, więc w przypadku listy wierszy potrzebujesz nowej macierzy.

PoczątkującyTablice i napisy

+10

Otrzymujesz macierz liczb całkowitych w postaci listy wierszy: matrix[i][j] to wartość w wierszu i, kolumnie j. Zwróć jej transpozycję: wartość z wiersza i, kolumny j przenosi się do wiersza j, kolumny i, tak aby każdy wiersz stał się kolumną. Macierz nie musi być kwadratowa: macierz m × n staje się macierzą n × m.

Funkcja

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

matrixinteger-2d-array: macierz m × n jako lista m wierszy zawierających n liczb całkowitych
Zwracainteger-2d-array: transpozycja o wymiarach n × m, jako lista n wierszy po m liczb całkowitych

Ograniczenia

1 ≤ m, n ≤ 1000, gdzie m = matrix.length i n = matrix[i].length
m × n ≤ 5000
Każdy wiersz ma tę samą długość n.
-1000 ≤ matrix[i][j] ≤ 1000

Przykłady

Wejście: matrix = [[1, 2, 3], [4, 5, 6]]
Wyjście: [[1, 4], [2, 5], [3, 6]]
Wyjaśnienie: Wiersz [1, 2, 3] staje się pierwszą kolumną, a [4, 5, 6] drugą. Odczytując wiersz po wierszu, otrzymujemy [1, 4], [2, 5], [3, 6]: macierz 3 × 2.

Pytanie dodatkowe

Załóżmy, że macierz jest przechowywana jako jedna płaska tablica wartości m × n, wiersz po wierszu. Czy potrafisz transponować macierz niekwadratową w tej tablicy, bez użycia drugiej tablicy?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Transponowanie niczego nie oblicza: wartość z pozycji (i, j) przenosi się na pozycję (j, i). Zmienia się kształt. Wynik ma n wierszy o długości m, więc nieskwadratowej listy wierszy nie można transponować w miejscu; utwórz nową macierz o zamienionych wymiarach i wypełnij ją.

Czytaj macierz kolumna po kolumnie

Intuicja

Wiersz j wyniku to kolumna j danych wejściowych, odczytywana od góry do dołu. Dla [[1, 2, 3], [4, 5, 6]] kolumna 0 zawiera kolejno 1 i 4, więc pierwszy wiersz wyniku to [1, 4].

Każda wartość jest odczytywana raz i zapisywana raz: czas O(m × n) i O(m × n) miejsca na wynik. Podczas budowania każdego nowego wiersza przeskakujesz przez wszystkie wiersze danych wejściowych, zamiast odczytywać wartości wzdłuż jednego wiersza — to wolniejszy sposób przeglądania pamięci.

Algorytm

Niech m oznacza liczbę wierszy, a n długość wiersza.
Dla każdej kolumny j od 0 do n-1 rozpocznij od pustej listy.
Dodaj do niej matrix[i][j] dla każdego i od 0 do m-1.
Dodaj listę do wyniku jako wiersz j i zwróć wynik po ostatniej kolumnie.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

Wypełnij nową siatkę n × m, odbijając lustrzanie każdą komórkę

Intuicja

Utwórz z góry wynik o rozmiarze n × m, a następnie odczytuj dane wejściowe w kolejności, w jakiej są zapisane, wiersz po wierszu, i umieszczaj każdą wartość pod jej lustrzanym adresem: result[j][i] = matrix[i][j]. To poprawne, ponieważ transpozycja polega dokładnie na zamianie tych indeksów, wykonanej raz dla każdej komórki.

Każda wartość jest kopiowana raz, więc złożoność czasowa wynosi O(m × n), a siatka zajmuje O(m × n) miejsca, którego wynik i tak potrzebuje. Odczytywanie wierszami odwiedza pamięć w zapisanej kolejności, a każdy wiersz wyniku jest alokowany raz, od razu w docelowym rozmiarze.

Algorytm

Niech m oznacza liczbę wierszy, a n długość wiersza.
Utwórz result z n wierszami, z których każdy zawiera m wartości.
Dla każdego wiersza i i każdej kolumny j danych wejściowych ustaw result[j][i] = matrix[i][j].
Zwróć result.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

Pułapki i przypadki brzegowe

Tworzenie wyniku o kształcie takim jak dane wejściowe. W przykładzie 2 × 3 zapisanie result[2][0] wykracza poza koniec: wynik potrzebuje n wierszy o długości m.
Zamiana miejscami matrix[i][j] i matrix[j][i] w miejscu. Działa to tylko wtedy, gdy m = n, i tylko dla komórek, w których j > i; pętla przechodząca przez każdą komórkę zamienia każdą parę dwa razy i zwraca niezmienioną macierz.
W Pythonie [[0] * m] * n tworzy n odwołań do jednej listy, więc zapisanie wartości w jednej komórce zmienia całą kolumnę. Twórz każdy wiersz osobno.
W C funkcja wywołująca odczytuje *returnSize jako liczbę wierszy wyniku, n, a (*returnColumnSizes)[j] jako długość każdego wiersza, m.

Najczęstsze pytania3

Co to jest transpozycja macierzy?

To macierz, którą otrzymujesz przez zamianę wierszy na kolumny: wartość w wierszu i, kolumnie j przenosi się do wiersza j, kolumny i. Macierz 2 × 3 staje się macierzą 3 × 2, a dwukrotna transpozycja daje z powrotem macierz wyjściową.

Jaka jest złożoność czasowa transponowania macierzy?

O(m × n): każda z m × n wartości jest kopiowana raz i nic mniej nie pozwoli uzyskać odpowiedzi. Nowa macierz zajmuje O(m × n) pamięci, tyle, ile wynosi rozmiar samego wyniku.

Czy możesz transponować macierz w miejscu?

W przypadku macierzy kwadratowej tak: zamień miejscami matrix[i][j] i matrix[j][i] dla każdej komórki powyżej przekątnej, używając dodatkowo O(1) pamięci. Macierz niekwadratowa zmienia kształt, więc w przypadku listy wierszy potrzebujesz nowej macierzy.

def transpose(matrix):
    # Wpisz kod tutaj

Test #1

Test #2

Argument

matrix = [[1, 2, 3], [4, 5, 6]]

Oczekiwany wynik

[[1, 4], [2, 5], [3, 6]]