[LeetCode]54. 螺旋矩阵(Spiral Matrix)

题目描述

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

示例 1:

输入:
[
[ 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, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路

  1. 解法一:旋转矩阵。与[剑指Offer]顺时针打印矩阵相同。
  2. 解法二:模拟螺旋路径。使用 visited 矩阵及右->下->左->上的顺序模拟螺旋的路径。
  3. 解法三:剥洋葱(按层模拟)。对于给定的矩阵四个角落的坐标,按照右->下->左->上的顺序把最外层剥离下来,再把矩阵的四个角落往内更新一层。

代码

Python 3.6

解法一:旋转矩阵

1
2
3
4
5
6
7
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
while matrix:
res += matrix.pop(0)
matrix = list(map(list, zip(*matrix)))[::-1]
return res

执行用时 : 52 ms
内存消耗 : 13.7 MB

解法二:模拟螺旋路径

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

visited = [[False] * cols for _ in range(rows)]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
di = 0 # 当前使用的方向
i, j = 0, 0 # 当前遍历的索引
for _ in range(rows * cols):
visited[i][j] = True
res.append(matrix[i][j])
x, y = i + dr[di], j + dc[di]
if 0 <= x < rows and 0 <= y < cols and not visited[x][y]:
i, j = x, y
else:
di = (di + 1) % 4
i += dr[di]
j += dc[di]
return res

执行用时 : 48 ms
内存消耗 : 13.7 MB

解法三:剥洋葱(按层模拟)

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
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
def spiral_coors(r1, r2, c1, c2):
for c in range(c1, c2 + 1):
yield r1, c
for r in range(r1 + 1, r2 + 1):
yield r, c2
if r1 < r2 and c1 < c2:
for c in range(c2 - 1, c1 - 1, -1):
yield r2, c
for r in range(r2 - 1, r1, -1):
yield r, c1
if not matrix:
return []
res = []
rows, cols = len(matrix), len(matrix[0])
r1 = c1 = 0
r2 = rows - 1
c2 = cols - 1
while r1 <= r2 and c1 <= c2:
for r, c in spiral_coors(r1, r2, c1, c2):
res.append(matrix[r][c])
r1 += 1
r2 -= 1
c1 += 1
c2 -= 1
return res

执行用时 : 48 ms
内存消耗 : 14 MB

参考

https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode