顺时针打印矩阵

题目描述

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

示例1:

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

示例2:

输入：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]

限制:

0 <= matrix.length <= 100

0 <= matrix[i].length <= 100

解题技巧

• 方法一:模拟

可以模拟打印矩阵的路径。初始位置是矩阵的左上角,初始方向是向右,当路径超出界限或者进入之前访问过的位置时,则顺时针旋转,进入下一个方向。

判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵$\textit{visited}$,其中的每个元素表示该位置是否被访问过。当一个元素被访问时,将$\textit{visited}$中的对应位置的元素设为已访问。

如何判断路径是否结束?由于矩阵中的每个元素都被访问一次,因此路径的长度即为矩阵中的元素数量,当路径的长度达到矩阵中的元素数量时即为完整路径,将该路径返回。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        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]):
                directionIndex = (directionIndex + 1) % 4
            row += directions[directionIndex][0]
            column += directions[directionIndex][1]
        return order

复杂度分析:

时间复杂度:$O(mn)$,其中m和n分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度:$O(mn)$。需要创建一个大小为$m \times n$的矩阵$\textit{visited}$记录每个位置是否被访问过。

• 方法二:按层模拟

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

定义矩阵的第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]]

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

1. 从左到右遍历上侧元素,依次为($\textit{top}$,$\textit{left}$)到($\textit{top}$,$\textit{right}$)。

2. 从上到下遍历右侧元素,依次为($\textit{top}$+1,$\textit{right}$)到($\textit{bottom}$,$\textit{right}$)。

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

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

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        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

复杂度分析:

时间复杂度：O(mn)O(mn)，其中 mm 和 nn 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度：O(1)O(1)。除了输出数组以外，空间复杂度是常数。