剑指offer-54

剑指 Offer 29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

实例

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

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

官方题解

方法一：模拟

class Solution:
    def spiralOrder(self, matrix):
        if not matrix or not matrix[0]:
            return list()
        
        rows,columns = len(matrix), len(matrix[0])

        visited = [[False] * columns for _ in range(rows)]
        total = rows * columns
        order = [0] * total

        # 向右，向下，向左，向上
        directions = [ [0,1], [1,0],[0,-1],[-1,0]]
        row, column = 0,0
        directionIndex = 0 # 初始先向右

        for i in range(total):
            order[i] = matrix[row][column] # 开始访问节点
            visited[row][column] = True #  标记节点已访问

            nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
            # 如果超过边界，或者访问过，则改变方向
            if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):
                print(nextRow,nextColumn)
                directionIndex = (directionIndex + 1) % 4
            
            row += directions[directionIndex][0]
            column += directions[directionIndex][1]
        return order

方法二：按层模拟

可以将矩阵看成若干层，首先打印最外层的元素，其次打印最外层的元素，直到打印最内层的元素。

定义矩阵的第 $k$ 层是到最近边界距离为 $k$ 的所有顶点。例如，下图矩阵最外层元素都是第 $1$ 层，次外层元素都是第 $2$ 层，剩下的元素都是第 $3$ 层。

[[1, 1, 1, 1, 1, 1, 1],
 [1, 2, 2, 2, 2, 2, 1],
 [1, 2, 3, 3, 3, 2, 1],
 [1, 2, 2, 2, 2, 2, 1],
 [1, 1, 1, 1, 1, 1, 1]]

对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 $(top, left)$，右上角位于 $(bottom, right)$，按照如下顺序遍历当前层的元素。

1、从左到右遍历上侧元素，依次为 $(top, left)$到 $(top, right)$。

2、从上到下遍历右侧元素，依次为 $(top+1,right)$ 到 $(bottom, right)$。

3、如果 $left<right$ 且 $top<bottom$，则从右到左遍历下侧元素，依次为 $(bottom, right-1)$ 到 $(bottom, left+1)$，以及从下到上遍历左侧元素，依次为 $(bottom,left)$到 $(top+1,left)$。

遍历完当前层的元素之后，将 $left$和$top$分别增加 $1$，将 $right$ 和 $bottom$ 分别减少 $1$，进入下一层继续遍历，直到遍历完所有元素为止。

class Solution:
    def spiralOrder(self, matrix):    
        if not matrix or not matrix[0]:
            return list()
        
        rows,columns = len(matrix), len(matrix[0])

        order = list()
        left,right,top,bottom = 0,columns-1, 0,rows-1
        while left<=right and top<= bottom:
            # 从左到右
            for column in range(left,right+1):
                order.append(matrix[top][column])
            
            # 从上到下
            for row in range(top+1,bottom+1):
                order.append(matrix[row][right])

            if left < right and top < bottom:
                # 从右到左
                for column in range(right-1,left,-1):
                    order.append(matrix[bottom][column])
                
                # 从下到上
                for row in range(bottom,top,-1):
                    order.append(matrix[row][left])
            
            left,right,top,bottom = left +1,right-1,top+1,bottom-1
        return order