Txing

欢迎来到 | 伽蓝之堂

0%

Q54-螺旋矩阵-中等-数组

Posted on In
Symbols count in article: 3.5k Reading time ≈ 3 mins.
Q54-螺旋矩阵-中等-数组

54. 螺旋矩阵

Question

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

Example 1:

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

Example 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]

Note:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= <= 100

Approach 1: 模拟

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    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]):
                directionIndex = (directionIndex + 1) % 4
            row += directions[directionIndex][0]
            column += directions[directionIndex][1]
        return order


def main():
    matrix = [[1,2,3],[4,5,6],[7,8,9]]
    solution=Solution().spiralOrder(matrix)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

  • 时间复杂度：，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

  • 空间复杂度：。需要创建一个大小为 的矩阵 记录每个位置是否被访问过。

Approach 2: 按层模拟

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

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

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

  • 从左到右遍历上侧元素，依次为 到 。

  • 从上到下遍历右侧元素，依次为 到 。

  • 如果 且 ，则从右到左遍历下侧元素，依次为 到 ，以及从下到上遍历左侧元素，依次为 到 。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

复杂度分析

  • 时间复杂度：，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
  • 空间复杂度：。除了输出数组以外，空间复杂度是常数。

Approach 3: 利用zip的简洁代码

1
2
3
4
5
6
7
8
9
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            # 移除第一行并返回移除元素
            res += matrix.pop(0)
            # zip(*Array) 可理解为解压，返回二维矩阵，把每一列打包
            matrix = list(zip(*matrix))[::-1]
        return res

复杂度分析

  • 时间复杂度：，其中 N 是 m 和 n 中最大值，调用 p 次zip()。因为函数调用时间复杂度是O(N)
  • 空间复杂度：。除了输出数组以外，空间复杂度是常数。