Python スパイラル行列トラバーサル
Python で 2D 行列の要素をスパイラル順に走査してリストします。
概要
スパイラル行列トラバーサルは、古典的な多次元配列の問題です。外側の境界を時計回りに移動し、境界を徐々に縮小する必要があります。
未訪問の行列部分の境界を追跡するために、「top」、「bottom」、「left」、「right」の 4 つのポインターを維持します。
左から右、上から下、右から左、下から上に順番に移動することで、すべてのセルを体系的にカバーします。
コードと実行の出力
インデックス操作を示す時計回りのスパイラル トラバーサル。
spiral.py
エディターで試してみるdef 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))端子出力
Matrix Spiral Order:
[1, 2, 3, 6, 9, 8, 7, 4, 5]段階的な実装
- 2D グラフィックス レンダリングとスパイラル パス トラッキング
- データ エンジンのグリッド レイアウト ナビゲーション パターン
- 高度なアルゴリズム評価テスト
よくある質問
スパイラルトラバーサルの時間計算量はどれくらいですか?
グリッド内のすべてのセルを 1 回だけ訪問するため、時間計算量は O(m * n) です。ここで、m は行、n は列です。