👻
【Python】スパイラルマトリックスの実装
はじめに
与えられた行列を螺旋状のリスト形式で返すアルゴリズムです。
参考図
実装
spiral_matrix.py
from typing import List
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# 出力配列を初期化
result = []
rows, columns = len(matrix), len(matrix[0])
# 上、右、下、左の境界をup、right、down、leftとして初期化
up = left = 0
right = columns - 1
down = rows - 1
# 要素をらせん状にトラバースし、各要素をresultに追加
while len(result) < rows * columns:
for col in range(left, right + 1):
result.append(matrix[up][col])
for row in range(up + 1, down + 1):
result.append(matrix[row][right])
if up != down:
for col in range(right - 1, left - 1, -1):
result.append(matrix[down][col])
if left != right:
for row in range(down - 1, up, -1):
result.append(matrix[row][left])
left += 1
right -= 1
up += 1
down -= 1
return result
# テスト
if __name__ == "__main__":
matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(Solution().spiralOrder(matrix))
参考
Discussion