题目

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

示例1

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

实现

思路1

该题其实就是将人脑思考螺旋输出矩阵的思路编程实现即可。
在稿纸上画个图，不难发现以下规律（其实也没啥规律）：

  • 首先螺旋顺序一定是顺时针，即轮流遍历上右下左四条边
  • 假设输入一个rows*columns的矩阵，一开始遍历最上边的时候，会遍历columns个元素；接着开始遍历右边，由于在遍历上边的时候，右上角的元素已被访问过了，所以此时遍历的rows=rows-1；同样的当右边遍历完，右下角的元素也是下边的其中一个元素，所以下边遍历的次数columns=columns-1；最后遍历左边，又会发现左边的遍历元素比右边的遍历元素少一个（左下角），所以遍历次数rows=rows-1。
  • 每次遍历一条边后可以检查一下rows-1或columns-1是否为0，若为零说明全部元素已经遍历结束了；若不为0则继续上面的循环。
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []

        rows, columns = len(matrix), len(matrix[0])
        total = rows * columns
        path = []
        x, y = 0, -1
        while True:
            # 遍历上方
            for j in range(0, columns):
                y = y + 1
                path.append(matrix[x][y])
            if rows-1==0:
                break
            else:
                rows -= 1

            # 遍历右方
            for j in range(0, rows):
                x = x + 1
                path.append(matrix[x][y])
            if columns-1==0:
                break
            else:
                columns -= 1

            # 遍历下方
            for j in range(0, columns):
                y = y - 1
                path.append(matrix[x][y])

            if rows-1==0:
                break
            else:
                rows -= 1

            # 遍历左方
            for j in range(0, rows):
                x = x - 1
                path.append(matrix[x][y])
            if columns-1==0:
                break
            else:
                columns -= 1

        return path

时间复杂度：，矩阵中每个元素都要被访问一次。