Spiral Matrix

Q: Apa kompleksitas waktu dan ruang dari Spiral Matrix?

Waktunya adalah O(m × n) , karena setiap nilai dibaca satu kali dan jawaban memuat setiap nilai. Mengupas lapisan dengan empat batas menggunakan memori tambahan O(1) . Penelusuran yang berbelok saat terhalang memerlukan grid sel yang telah dikunjungi berukuran O(m × n) .

Q: Bagaimana cara menghindari membaca sebuah nilai dua kali saat melakukan penelusuran spiral?

Mulai setiap sisi satu sel setelah sisi sebelumnya berakhir, sehingga setiap sudut menjadi bagian dari satu sisi. Pada lapisan yang tebalnya satu baris atau satu kolom, lewati baris bawah dan kolom kiri.

Q: Bagaimana cara mengisi matriks dalam urutan spiral, bukan membacanya?

Gunakan empat batas dan sisi yang sama, tetapi tulis, bukan baca. Simpan pencacah yang dimulai dari 1 ke setiap sel saat kamu melewatinya, lalu tambahkan satu setiap kali. Untuk matriks n × n , pencacah berakhir di n² .

SedangMatematika dan simulasi Array dan string

+10

Kamu mendapatkan matriks bilangan bulat dengan m baris dan n kolom, yang diberikan sebagai list baris. Kembalikan semua nilainya dalam urutan spiral.

Mulai dari sudut kiri atas dan bergerak ke kanan sepanjang baris teratas, lalu ke bawah sepanjang kolom paling kanan, ke kiri sepanjang baris terbawah, dan ke atas sepanjang kolom paling kiri. Terus bergerak melingkar ke dalam searah jarum jam sampai setiap nilai dibaca tepat satu kali.

Fungsi

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

matrixinteger-2d-array: grid berisi bilangan bulat, berupa list baris yang panjangnya sama
Mengembalikaninteger-array: setiap nilai matriks dalam urutan spiral searah jarum jam, dimulai dari sudut kiri atas

Batasan

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

Contoh

Input: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Penjelasan: Nilainya bertambah mengikuti spiral. Cincin luar terbaca dari 1 hingga 10, dan lapisan dalam berupa satu kolom, dibaca sekali: 11, 12.

Input: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Output: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Penjelasan: Cincin terluar memberikan 7, 1, 5, 3, 6, -1, 4, 0, 8, 2. Yang tersisa adalah satu baris 9, -4, dibaca sekali dari kiri ke kanan.

Pertanyaan lanjutan

Bisakah kamu mengembalikan nilai dalam urutan berlawanan arah jarum jam, dimulai dari sudut kiri atas lalu menyusuri kolom kiri terlebih dahulu?

Petunjuk

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

0 dari 3 dibuka

Solusi

Masalahnya adalah pencatatan. Setiap sudut harus dibaca satu kali, dan lapisan paling dalam bisa berupa satu baris atau kolom, sehingga satu putaran penuh akan membaca ulang nilai. Kamu bisa berjalan dan berbelok ke kanan setiap kali terhalang, atau mengupas matriks satu cincin setiap kali dengan empat batas yang terus menyusut dan tanpa memori tambahan.

Berjalanlah dan belok kanan saat terhalang

Intuisi

Seorang pejalan mulai dari sel kiri atas, menghadap ke kanan, dan membaca setiap sel yang diinjaknya. Jika langkah berikutnya akan keluar dari matriks atau menuju sel yang sudah dibaca, ia berbelok ke kanan. Tepi matriks menghentikan putaran pertama, dan sel-sel yang telah dibaca menjadi penghalang untuk setiap putaran berikutnya, sehingga setiap putaran tetap berada di dalam putaran sebelumnya.

Pada contoh pertama, pejalan membaca 1 hingga 10 di sekeliling tepi. Di atas 10 terdapat 1 yang sudah dibaca, jadi ia berbelok menuju 11, lalu turun menuju 12. Jalankan perulangan tepat m × n kali dan kamu tidak perlu mendeteksi akhirnya. Waktunya adalah O(m × n), dan grid seen membutuhkan memori tambahan sebesar O(m × n).

Algoritma

Mulai dari baris 0, kolom 0, indeks arah d = 0, dengan dr = [0, 1, 0, -1], dc = [1, 0, -1, 0], dan kisi seen yang semua nilainya false.
Ulangi sebanyak m × n kali: tambahkan nilai saat ini dan tandai selnya sebagai sudah dikunjungi.
Jika sel berikutnya berada di luar matriks atau sudah dikunjungi, berbelok dengan d = (d+1) % 4.
Bergerak satu langkah ke arah d.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

Kupas lapisannya dengan empat batas

Intuisi

Jelaskan lapisan saat ini dengan baris top hingga bottom dan kolom left hingga right. Setiap sisi putaran dimulai satu sel setelah ujung sisi sebelumnya, sehingga setiap sudut dibaca satu kali. Lalu geser keempat batas ke dalam.

Lapisan yang tebalnya satu baris atau satu kolom akan memutus putaran. Pada contoh kedua, lapisan terakhir adalah baris 9, -4: baris atas membaca kedua nilai, dan menelusuri kembali baris bawah akan menambahkan 9 lagi. Pada contoh ketiga, menelusuri kembali satu kolom ke atas akan membaca ulang 1. Jadi, telusuri baris bawah dan kolom kiri hanya jika top < bottom dan left < right.

Setiap nilai dibaca satu kali, jadi kompleksitas waktunya adalah O(m × n), dan memori tambahannya adalah empat bilangan bulat.

Algoritma

Tetapkan top = 0, bottom = m-1, left = 0, right = n-1.
Selama top ≤ bottom dan left ≤ right, baca baris teratas dari left hingga right dan kolom paling kanan dari top+1 hingga bottom.
Jika top < bottom dan left < right, baca baris terbawah dari right-1 hingga left dan kolom paling kiri dari bottom-1 hingga top+1.
Tambahkan satu ke top dan left, kurangi satu dari bottom dan right.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

Jebakan dan kasus tepi

Melewatkan pemeriksaan top < bottom dan left < right. Contoh kedua kemudian berakhir dengan 9, -4, 9 dan contoh ketiga menghasilkan 4, 1, 7, 1.
Menelusuri setiap sisi dari sel pertamanya hingga sel terakhirnya. Setiap sudut kemudian dibaca dua kali.
Melakukan perulangan selama top < bottom. Dalam matriks 3 × 3, nilai tengah tidak pernah dibaca.
Menggunakan matrix.length untuk kedua batas. Cara ini berhasil untuk setiap masukan persegi dan gagal untuk masukan 3 × 4.
Di R, 3:2 menghasilkan 3, 2, bukan rentang kosong; tambahkan pemeriksaan atau gunakan seq_len. Di Lua dan R, indeks dimulai dari 1.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dan ruang dari Spiral Matrix?

Waktunya adalah O(m × n), karena setiap nilai dibaca satu kali dan jawaban memuat setiap nilai. Mengupas lapisan dengan empat batas menggunakan memori tambahan O(1). Penelusuran yang berbelok saat terhalang memerlukan grid sel yang telah dikunjungi berukuran O(m × n).

Bagaimana cara menghindari membaca sebuah nilai dua kali saat melakukan penelusuran spiral?

Mulai setiap sisi satu sel setelah sisi sebelumnya berakhir, sehingga setiap sudut menjadi bagian dari satu sisi. Pada lapisan yang tebalnya satu baris atau satu kolom, lewati baris bawah dan kolom kiri.

Bagaimana cara mengisi matriks dalam urutan spiral, bukan membacanya?

Gunakan empat batas dan sisi yang sama, tetapi tulis, bukan baca. Simpan pencacah yang dimulai dari 1 ke setiap sel saat kamu melewatinya, lalu tambahkan satu setiap kali. Untuk matriks n × n, pencacah berakhir di n².

def spiralOrder(matrix):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

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