LeetCode 54. Spiral Matrix 2019-06-15

题目描述

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

tag

矩阵遍历题 矩阵 模拟

样例

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

(模拟) O(mn)
思路

用dr = [0, 1, 0, -1],dc = [1, 0, -1, 0]来描述方向。
每次遍历后枚举下一个可行的方向是哪个,可行是指下一个位置没有被访问过。如果四个方向都不可行,则遍历结束。一个遍历 m * n次。

复杂度分析:
python 代码
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
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []
R = len(matrix)
C = len(matrix[0])
visited = [[False] * C for _ in matrix]
res = []
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
r = 0
c = 0
dire = 0
for _ in range(R * C):
res.append(matrix[r][c])
visited[r][c] = True
nr = r + dr[dire]
nc = c + dc[dire]
if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc]:
r = nr
c = nc
else:
dire = (dire + 1) % 4
r = r + dr[dire]
c = c + dc[dire]
return res