54. 螺旋矩阵

题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:

输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路

1.模拟螺旋矩阵的输出方式，从左上角进入，当路径超出边界或元素已被访问，则顺时针旋转，进入下一个方向。
2.按照层次输出，先输出最外面一层，再进入次一层，直到输出所有元素。

代码

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # if not matrix or not matrix[0]:
        #     return list()
        # rows, colunmns = len(matrix), len(matrix[0])
        # direc = [(0,1),(1,0),(0,-1),(-1,0)]
        # direcIndex = 0
        # total = rows*colunmns
        # visited = [[0]*colunmns for _ in range(rows)]
        # row, column = 0, 0
        # nums = [0]*total
        # for i in range(total):
        #     visited[row][column] = 1
        #     nums[i] = matrix[row][column]
        #     newrow, newcolumn = row+direc[direcIndex][0], column+direc[direcIndex][1]
        #     if not (0 <= newrow < rows and 0 <= newcolumn < colunmns and not visited[newrow][newcolumn]):
        #         direcIndex = (direcIndex+1)%4
        #     row += direc[direcIndex][0]
        #     column += direc[direcIndex][1]
        # return nums

        if not matrix:
            return []
        top, bottom, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1
        nums = []
        while True:
            #从左到右 left~right
            for i in range(left, right+1):
                nums.append(matrix[left][i])
            #向下一层
            top +=1
            if top>bottom:
                break

            #从上到下 top~bottom
            for i in range(top, bottom+1):
                nums.append(matrix[i][right])
            #向左一层
            right -= 1
            if left>right:
                break

            #从左到右 right~left
            for i in range(right, left-1, -1):
                nums.append(matrix[bottom][i])
            #向上一层
            bottom -= 1
            if top>bottom:
                break

            #从下到上 bottom~top
            for i in range(bottom, top-1, -1):
                nums.append(matrix[i][left])
            #向右一层
            left += 1
            if left>right:
                break
        return nums