Rotate Image

Q: Apa kompleksitas waktu dan ruang untuk merotasi matriks?

Memutar matriks n × n memerlukan waktu O(n²), karena hampir setiap nilai harus dipindahkan satu kali. Metode transpose lalu membalik memerlukan ruang tambahan O(1). Membuat salinan yang sudah diputar juga memerlukan waktu O(n²), tetapi menggunakan ruang tambahan O(n²).

SedangArray dan string Matematika dan simulasi

+10

Kamu diberi grid n × n berisi bilangan bulat, dengan satu list untuk setiap baris. Putar grid seperempat putaran searah jarum jam dan kembalikan. Baris paling atas menjadi kolom paling kanan, baris kedua menjadi kolom di sebelah kirinya, dan seterusnya: nilai di (i, j) berpindah ke (j, n-1-i). Kamu boleh mengubah grid secara langsung, lalu kembalikan.

Fungsi

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

matrixinteger-2d-array: grid persegi, satu list bagian dalam untuk setiap baris
Mengembalikaninteger-2d-array: matriks diputar 90 derajat searah jarum jam

Batasan

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

Contoh

Input: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Output: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Penjelasan: Baris pertama, 3 7 1, menjadi kolom terakhir, dibaca dari atas ke bawah. Kolom pertama, 3 9 4, dibaca dari bawah ke atas, menjadi baris pertama [4, 9, 3]. Nilai tengah 5 tetap di tempatnya.

Pertanyaan lanjutan

Langkah in-place apa saja yang memutar matriks 180 derajat, dan bisakah kamu melakukannya dalam satu kali lintasan pertukaran?

Petunjuk

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

0 dari 3 dibuka

Solusi

Ke mana setiap nilai berpindah ditentukan oleh rumus: (i, j) berpindah ke (j, n-1-i). Bagian sulitnya adalah memindahkan nilai tanpa matriks kedua, karena menulis nilai ke sel barunya akan menimpa nilai yang belum dipindahkan. Transposisi yang dilanjutkan dengan pembalikan baris menghasilkan putaran seperempat yang sama melalui pertukaran berpasangan.

Buat salinan yang diputar

Intuisi

Baris i menjadi kolom n-1-i, dan nilai pada posisi j di baris tersebut berada di posisi j ke bawah pada kolom itu, yaitu baris j. Jadi, result[j][n-1-i] = matrix[i][j]. Pada contoh pertama, angka 4 di baris 2, kolom 0 berpindah ke baris 0, kolom 0, itulah sebabnya jawaban dimulai dengan 4.

Nilai-nilai tersebut berpindah dalam siklus berisi empat nilai, jadi menulis langsung di tempatnya akan menghapus sebuah nilai sebelum nilai itu berpindah: angka 3 akan menimpa angka 1 di pojok kanan atas. Salinan membutuhkan n² sel tambahan, 4,900 untuk n = 70.

Algoritma

Buat matriks hasil berukuran n × n.
Untuk setiap baris i dan kolom j, salin matrix[i][j] ke result[j][n-1-i].
Kembalikan hasilnya.

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

Transpose, lalu balik setiap baris

Intuisi

Transposisi memindahkan (i, j) ke (j, i), dan membalik baris memindahkan kolom c ke kolom n-1-c. Jika digabungkan, keduanya memindahkan (i, j) ke (j, n-1-i), tepat ke posisi yang dituju rotasi.

Kedua langkah berjalan langsung di tempat karena masing-masing terdiri dari pertukaran pasangan. Dalam transposisi, matrix[i][j] dan matrix[j][i] masing-masing seharusnya berada di sel yang lain, jadi satu pertukaran menyelesaikan keduanya. Tukar hanya pasangan dengan j > i, atau setiap pasangan akan ditukar kembali. Membalik baris menukar kedua ujungnya, lalu bergerak ke arah tengah.

Pada contoh pertama, transposisi menghasilkan [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: setiap baris kini memuat kolom dari matriks sebelumnya. Membalik setiap baris menghasilkan jawaban.

Transposisi melakukan n(n-1)/2 pertukaran dan pembalikan melakukan n·⌊n/2⌋ pertukaran, jadi pekerjaannya adalah O(n²) dengan beberapa variabel sebagai memori tambahan. Versi R terlebih dahulu menyalin input ke dalam matriks R, sehingga memori tambahannya adalah O(n²).

Algoritma

Untuk setiap sel di atas diagonal utama, (i, j) dengan j > i, tukar nilainya dengan nilai sel (j, i).
Untuk setiap baris, tukar nilai pertama dan terakhirnya, lalu gerakkan kedua ujungnya ke dalam hingga bertemu.
Kembalikan matriks.

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

Jebakan dan kasus tepi

Melakukan transpose dengan j dimulai dari 0. Setiap pasangan ditukar dua kali, sehingga efeknya saling meniadakan. Hasilnya hanya baris yang dibalik, seperti bayangan cermin.
Membalik sebelum melakukan transpose. Urutan itu memutar matriks berlawanan arah jarum jam. Uji matriks 2 × 2 dapat mendeteksi kesalahan ini: [[1, 2], [3, 4]] harus menjadi [[3, 1], [4, 2]].
Menulis matrix[j][n-1-i] = matrix[i][j] ke matriks yang sama. Sel tujuan masih menyimpan nilai yang belum dipindahkan, sehingga nilai itu hilang.
Menggunakan n-i alih-alih n-1-i. Dengan indeks berbasis 0, kolom terakhir adalah n-1, jadi n-i melewati batas untuk i = 0.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dan ruang untuk merotasi matriks?

Memutar matriks n × n memerlukan waktu O(n²), karena hampir setiap nilai harus dipindahkan satu kali. Metode transpose lalu membalik memerlukan ruang tambahan O(1). Membuat salinan yang sudah diputar juga memerlukan waktu O(n²), tetapi menggunakan ruang tambahan O(n²).

Bagaimana cara memutar matriks berlawanan arah jarum jam?

Tukar urutan kedua langkah: balikkan setiap baris terlebih dahulu, lalu lakukan transpose. Kamu juga bisa melakukan transpose, lalu membalik urutan baris. Dengan cara apa pun, nilai di (i, j) berakhir di (n-1-j, i).

Bisakah kamu memutar matriks dengan memindahkan empat nilai sekaligus?

Ya. Setiap nilai di luar bagian tengah termasuk dalam siklus yang terdiri dari empat sel: (i, j), (j, n-1-i), (n-1-i, n-1-j), dan (n-1-j, i). Dari satu ring ke ring berikutnya, simpan satu nilai dari setiap siklus dalam variabel, lalu geser tiga nilai lainnya. Kompleksitas waktunya tetap O(n²) dan penggunaan ruangnya O(1), tetapi ada lebih banyak operasi indeks yang bisa keliru.

def rotateImage(matrix):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

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

Output yang diharapkan

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