Penjelajahan Matriks Spiral Python
Lintasi dan buat daftar elemen matriks 2D dalam urutan spiral dengan Python.
Ikhtisar
Penjelajahan matriks spiral adalah masalah array multidimensi klasik. Hal ini memerlukan melintasi batas luar searah jarum jam dan secara bertahap memperkecil batas tersebut.
Kami mempertahankan empat petunjuk: `atas`, `bawah`, `kiri`, dan `kanan` untuk melacak batas bagian matriks yang belum dikunjungi.
Dengan menelusuri dari kiri ke kanan, atas ke bawah, kanan ke kiri, dan bawah ke atas secara berurutan, kita mencakup semua sel secara sistematis.
Kode & Output Eksekusi
Traversal spiral searah jarum jam menunjukkan manipulasi indeks.
spiral.py
Coba di Editordef spiral_order(matrix):
if not matrix:
return []
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# Traverse Right
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Traverse Down
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
if top <= bottom:
# Traverse Left
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
if left <= right:
# Traverse Up
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print("Matrix Spiral Order:")
print(spiral_order(grid))Keluaran Terminal
Matrix Spiral Order:
[1, 2, 3, 6, 9, 8, 7, 4, 5]Implementasi Langkah demi Langkah
- Render grafis 2D dan pelacakan jalur spiral
- Pola navigasi tata letak grid di mesin data
- Tes penilaian algoritma tingkat lanjut
Pertanyaan yang Sering Diajukan
Berapa kompleksitas waktu dari penjelajahan spiral?
Kompleksitas waktunya adalah O(m * n) dengan m adalah baris dan n adalah kolom, karena kita mengunjungi setiap sel dalam grid tepat satu kali.