Transpose Matrix

Q: Berapa kompleksitas waktu untuk mentransposisi matriks?

O(m × n) : setiap nilai m × n disalin satu kali, dan tidak ada yang lebih sedikit yang dapat menghasilkan jawaban. Matriks baru membutuhkan ruang O(m × n) , sebesar ukuran output itu sendiri.

Q: Bisakah kamu melakukan transpose matriks secara langsung?

Untuk matriks persegi, ya: tukar matrix[i][j] dengan matrix[j][i] untuk setiap sel di atas diagonal, dengan memori tambahan O(1) . Matriks yang tidak persegi berubah bentuk, jadi jika menggunakan list baris, kamu memerlukan matriks baru.

PemulaArray dan string

+10

Kamu menerima matriks bilangan bulat sebagai list baris: matrix[i][j] adalah nilai pada baris i, kolom j. Kembalikan transposenya: nilai pada baris i, kolom j berpindah ke baris j, kolom i, sehingga setiap baris menjadi kolom. Matriks tidak harus berbentuk persegi: matriks m × n menjadi matriks n × m.

Fungsi

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

matrixinteger-2d-array: matriks m × n, sebagai list yang terdiri dari m baris berisi n bilangan bulat
Mengembalikaninteger-2d-array: transpose berukuran n × m, sebagai list yang terdiri dari n baris berisi m bilangan bulat

Batasan

1 ≤ m, n ≤ 1000, dengan m = matrix.length dan n = matrix[i].length
m × n ≤ 5000
Setiap baris memiliki panjang yang sama, yaitu n.
-1000 ≤ matrix[i][j] ≤ 1000

Contoh

Input: matrix = [[1, 2, 3], [4, 5, 6]]
Output: [[1, 4], [2, 5], [3, 6]]
Penjelasan: Baris [1, 2, 3] menjadi kolom pertama dan [4, 5, 6] menjadi kolom kedua. Jika dibaca baris demi baris, hasilnya adalah [1, 4], [2, 5], [3, 6]: matriks 3 × 2.

Pertanyaan lanjutan

Misalkan matriks disimpan sebagai satu array datar yang berisi m × n nilai, baris demi baris. Bisakah kamu mentransposisi matriks nonpersegi di dalam array tersebut tanpa array kedua?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Transposisi tidak menghitung apa pun: nilai pada (i, j) berpindah ke (j, i). Yang berubah adalah bentuknya. Hasilnya memiliki n baris dengan panjang m, jadi list baris yang tidak berbentuk persegi tidak dapat ditransposisikan langsung; buat matriks baru dengan ukuran yang ditukar, lalu isi.

Baca matriks satu kolom setiap kali

Intuisi

Baris j pada jawaban adalah kolom j pada input, dibaca dari atas ke bawah. Untuk [[1, 2, 3], [4, 5, 6]], kolom 0 dibaca 1 lalu 4, jadi baris pertama jawaban adalah [1, 4].

Setiap nilai dibaca sekali dan ditulis sekali: waktu O(m × n), dan ruang O(m × n) untuk hasilnya. Saat membangun setiap baris baru, kamu melompati setiap baris input alih-alih membacanya satu per satu, yang merupakan cara lebih lambat untuk mengakses memori.

Algoritma

Misalkan m adalah jumlah baris dan n adalah panjang satu baris.
Untuk setiap kolom j dari 0 hingga n-1, mulai dengan list kosong.
Tambahkan matrix[i][j] ke dalamnya untuk setiap i dari 0 hingga m-1.
Tambahkan list tersebut ke hasil sebagai baris j, lalu kembalikan hasil setelah kolom terakhir.

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

Isi grid n × m baru dengan mencerminkan setiap sel

Intuisi

Buat hasil berukuran n × m terlebih dahulu, lalu baca input sesuai urutan penyimpanannya, baris demi baris, dan tempatkan setiap nilai pada alamat cerminnya: result[j][i] = matrix[i][j]. Ini benar karena transposisi tepat merupakan pertukaran indeks ini, yang diterapkan sekali pada setiap sel.

Setiap nilai disalin satu kali, jadi waktunya adalah O(m × n), dan matriks memerlukan ruang O(m × n) untuk output. Membaca sepanjang baris mengunjungi memori sesuai urutan penyimpanannya, dan setiap baris hasil dialokasikan satu kali dengan ukuran akhirnya.

Algoritma

Misalkan m adalah jumlah baris dan n adalah panjang satu baris.
Buat result dengan n baris, masing-masing berisi m nilai.
Untuk setiap baris i dan setiap kolom j pada input, tetapkan result[j][i] = matrix[i][j].
Kembalikan 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

Jebakan dan kasus tepi

Membuat hasil dengan bentuk yang sama seperti input. Untuk contoh 2 × 3, menulis result[2][0] mengakses indeks di luar batas: hasilnya memerlukan n baris yang masing-masing memiliki panjang m.
Menukar matrix[i][j] dengan matrix[j][i] secara langsung. Cara ini hanya berlaku jika m = n, dan hanya untuk sel dengan j > i; perulangan pada setiap sel akan menukar setiap pasangan dua kali dan mengembalikan matriks seperti semula.
Di Python, [[0] * m] * n membuat n referensi ke satu list, jadi menulis satu sel akan mengubah seluruh kolom. Buat setiap baris secara terpisah.
Di C, pemanggil membaca *returnSize sebagai jumlah baris hasil, n, dan (*returnColumnSizes)[j] sebagai panjang setiap baris, m.

Pertanyaan yang sering diajukan3

Apa transpose dari sebuah matriks?

Ini adalah matriks yang kamu dapatkan dengan menukar baris dan kolom: nilai pada baris i, kolom j berpindah ke baris j, kolom i. Matriks 2 × 3 menjadi 3 × 2, dan mentranspos matriks dua kali akan menghasilkan matriks semula.

Berapa kompleksitas waktu untuk mentransposisi matriks?

O(m × n): setiap nilai m × n disalin satu kali, dan tidak ada yang lebih sedikit yang dapat menghasilkan jawaban. Matriks baru membutuhkan ruang O(m × n), sebesar ukuran output itu sendiri.

Bisakah kamu melakukan transpose matriks secara langsung?

Untuk matriks persegi, ya: tukar matrix[i][j] dengan matrix[j][i] untuk setiap sel di atas diagonal, dengan memori tambahan O(1). Matriks yang tidak persegi berubah bentuk, jadi jika menggunakan list baris, kamu memerlukan matriks baru.

def transpose(matrix):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

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

Output yang diharapkan

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