👻

【Python】スパイラルマトリックスの実装

2023/05/13に公開

はじめに

与えられた行列を螺旋状のリスト形式で返すアルゴリズムです。

参考図

実装

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))

参考

https://leetcode.com/problems/spiral-matrix/editorial/

Discussion