Transpose Matrix

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

To O(m × n) , ponieważ każda z m × n wartości jest kopiowana raz i nic mniej nie wystarczy do uzyskania odpowiedzi. Nowa macierz zajmuje O(m × n) miejsca, czyli tyle, ile sam wynik.

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

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

Q: Jak transponować niekwadratową macierz?

Utwórz wynik z n wierszami o długości m , podczas gdy dane wejściowe mają m wierszy o długości n . Następnie skopiuj każdą wartość za pomocą result[j][i] = matrix[i][j] . Pomysł z przekątną nie ma zastosowania w przypadku prostokąta, ponieważ obie macierze mają różne wymiary.

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ę, czyli macierz otrzymaną przez zamianę każdego wiersza w kolumnę. Wartość z wiersza i, kolumny j przenosi się do wiersza j, kolumny i. 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 macierzy n × m jako lista n wierszy zawierających 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: Pierwszy wiersz [1, 2, 3] staje się pierwszą kolumną, a [4, 5, 6] drugą. Odczytując wynik wiersz po wierszu, otrzymujemy [1, 4], [2, 5], [3, 6]: macierz 2 × 3 zmieniła się w macierz 3 × 2.

+15 ukrytych testów przy wysłaniu

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

Transpozycja to czysta zmiana adresu: wartość z (i, j) przenosi się do (j, i) i nic nie jest obliczane. Trzeba zadbać o prawidłowy kształt. Macierzy niekwadratowej przechowywanej jako lista wierszy nie można transponować w miejscu, ponieważ wynik ma n wierszy o długości m zamiast m wierszy o długości n, więc tworzysz nową macierz o zamienionych wymiarach i ją wypełniasz.

Odczytuj macierz kolumna po kolumnie

Intuicja

Wiersz j wyniku to kolumna j danych wejściowych, odczytywana z góry na dół. Zbuduj więc wynik po jednym wierszu naraz: dla każdej kolumny j od 0 do n-1 zbierz matrix[0][j], matrix[1][j] i tak dalej, aż do matrix[m-1][j], a następnie dodaj tę listę jako kolejny wiersz.

Dla [[1, 2, 3], [4, 5, 6]] kolumna 0 zawiera kolejno 1 i 4, kolumna 1 — 2 i 5, a kolumna 2 — 3 i 6. Wynik to [[1, 4], [2, 5], [3, 6]], z n = 3 wierszami po m = 2 wartości.

Każda wartość jest odczytywana raz i zapisywana raz, więc czas działania wynosi O(m × n), a wynik zajmuje O(m × n) pamięci. Koszt wynika ze sposobu dostępu: tworzenie jednego nowego wiersza wymaga przejścia przez każdy wiersz danych wejściowych — przeskakiwania między wierszami zamiast odczytywania kolejnych elementów w jednym wierszu.

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

Najpierw ustal kształt, a potem wypełnij tablicę. Wynik ma n wierszy o długości m, więc utwórz tę siatkę od razu. Następnie odczytuj dane wejściowe w ich naturalnej kolejności, wiersz po wierszu i od lewej do prawej, i umieszczaj każdą wartość pod lustrzanym adresem: result[j][i] = matrix[i][j].

Ta reguła jest poprawna, ponieważ transponowanie polega dokładnie na zamianie tych dwóch indeksów. W przykładzie z kwadratową tablicą [[1, 2], [3, 4]] liczby 1 i 4 na przekątnej pozostają na swoich miejscach, 2 przechodzi z (0, 1) na (1, 0), a 3 z (1, 0) na (0, 1), dając [[1, 3], [2, 4]].

Każda z m × n wartości jest kopiowana raz, więc złożoność czasowa wynosi O(m × n), a nowa siatka zajmuje O(m × n) pamięci, której i tak wymaga wynik. Odczytywanie danych wejściowych wierszami odwiedza pamięć w kolejności, w jakiej jest przechowywana, a każdy wiersz wyniku jest tworzony 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

Prawie każda błędna odpowiedź wynika z kształtu, a nie z wartości.

Tworzenie wyniku o takim samym kształcie jak dane wejściowe. Wynik o m wierszach i n kolumnach działa tylko dla macierzy kwadratowej; w przykładzie 2 × 3 zapisanie result[2][0] wykracza poza zakres. Wynik powinien mieć n wierszy o długości m.
Zamiana elementów miejscami w macierzy niekwadratowej. Zamiana matrix[i][j] z matrix[j][i] działa tylko wtedy, gdy m = n, a nawet wtedy pętla musi obejmować tylko komórki nad przekątną (j > i), w przeciwnym razie każda para zostanie zamieniona dwa razy i macierz wróci do pierwotnego stanu.
Współdzielenie jednego obiektu wiersza. W Pythonie [[0] * m] * n tworzy n odwołań do tej samej listy, więc zapisanie wartości w jednej komórce zmienia całą kolumnę. Twórz każdy wiersz osobno.
Zapominanie o rozmiarach kolumn w C. Kod wywołujący odczytuje *returnSize jako liczbę wierszy wyniku, n, a (*returnColumnSizes)[j] jako długość każdego wiersza, m.

Najczęstsze pytania4

Co to jest transpozycja macierzy?

To macierz, którą otrzymujesz po zamianie wierszy na kolumny: wartość z wiersza i, kolumny j przenosi się do wiersza j, kolumny i. Macierz 2 × 3 staje się macierzą 3 × 2, a dwukrotna transpozycja przywraca macierz początkową.

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

To O(m × n), ponieważ każda z m × n wartości jest kopiowana raz i nic mniej nie wystarczy do uzyskania odpowiedzi. Nowa macierz zajmuje O(m × n) miejsca, czyli tyle, ile sam wynik.

Czy możesz transponować macierz w miejscu?

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

Jak transponować niekwadratową macierz?

Utwórz wynik z n wierszami o długości m, podczas gdy dane wejściowe mają m wierszy o długości n. Następnie skopiuj każdą wartość za pomocą result[j][i] = matrix[i][j]. Pomysł z przekątną nie ma zastosowania w przypadku prostokąta, ponieważ obie macierze mają różne wymiary.

Python

def transpose(matrix):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

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

Oczekiwane

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