题目描述

[EN | CN]

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

示例 1:

1
2
3
4
5
6
7
输入:
[
 [ 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
输入:
[
  [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:直接法

按照顺时针螺旋的顺序来取一个二维数组,那么取的顺序应该是往右→往下→往左→往上,直到最终左右相遇或上下相遇。

直接的做法就是使用一个 while True,里面按照这四种方向取一行或者一列,取完之后判断一下是否满足退出条件,或者换下一个方向。

假设数组行数、列数分别为 $m$、$n$,那么

  • 时间复杂度为 $O(mn)$,遍历;
  • 空间复杂度为 $O(mn)$,保存结果。

实现与结果如下:

 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
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return []

        h, w, ret = len(matrix), len(matrix[0]), []
        l, r, u, d = 0, w - 1, 0, h - 1

        while True:
            ret.extend([matrix[u][i] for i in range(l, r + 1)])
            if u == d:
                break
            u += 1

            ret.extend([matrix[i][r] for i in range(u, d + 1)])
            if r == l:
                break
            r -= 1

            ret.extend([matrix[d][i] for i in range(r, l - 1, -1)])
            if d == u:
                break
            d -= 1

            ret.extend([matrix[i][l] for i in range(d, u - 1, -1)])
            if l == r:
                break
            l += 1
        return ret
  • 执行用时:40 ms,在所有 Python3 提交中击败了 61.63% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 6.25% 的用户。

解法 2:解法 1 的简化写法

解法 1 中 4 个方向的 extend 其实可以写到一起,这样看起来简洁很多,复杂度不变。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return []

        h, w, ret = len(matrix), len(matrix[0]), []
        l, r, u, d = 0, w - 1, 0, h - 1

        while l < r and u < d:
            ret.extend([matrix[u][i] for i in range(l, r)])
            ret.extend([matrix[i][r] for i in range(u, d)])
            ret.extend([matrix[d][i] for i in range(r, l, -1)])
            ret.extend([matrix[i][l] for i in range(d, u, -1)])
            u, d, l, r = u + 1, d - 1, l + 1, r - 1

        if u == d:
            ret.extend([matrix[u][i] for i in range(l, r + 1)])
        elif l == r:
            ret.extend([matrix[i][r] for i in range(u, d + 1)])

        return ret
  • 执行用时:40 ms,在所有 Python3 提交中击败了 61.63% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 6.25% 的用户。

解法 3:递归

我们尝试简化问题,每次我们只取 matrix 的第一行,然后把 matrix 剩下的部分 逆时针旋转 90° 进行下一次递归,这里的几个值得注意的地方:

  1. 如何判断递归结束?我们可以利用了 return x and y 的写法:
    • 如果 x 为空数组,就会直接返回 [],
    • 如果 x 为非空数组,就会返回 y。
  2. 如何旋转一个二维数组?可以参考《LeetCode 48. 旋转图像 ⌨️》。

由于旋转操作的存在,时间复杂度会比较高。

1
2
3
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        return matrix and [*matrix.pop(0)] + self.spiralOrder(list(zip(*matrix))[::-1])
  • 执行用时:40 ms,在所有 Python3 提交中击败了 61.63% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 6.25% 的用户。
▲