1.题目描述:给你一个 m
行 n
列的矩阵 matrix
,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素
2.运行示例:
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
3.解题思路
题意要求我们螺旋向内遍历矩阵,需要考虑以下几个问题:
3.1. 起始位置
3.2. 移动方向
3.3. 边界
3.4. 结束条件
3.1. 起始位置
螺旋矩阵的遍历起点是矩阵的左上角,也就是 (0, 0) 位置。
3.2. 移动方向
起始位置的下一个移动方向是向右。在遍历的过程中,移动方向是固定的:
右 → ,下↓,左←,上↑
右→,下↓,左←,上↑
移动方向是按照上面的顺序循环进行的。每次当移动到了边界,才会更改方向。但边界并不是固定的,请看下面分析。
3.3. 边界
本题的边界是最大的难点,因为是随着遍历的过程而变化的。螺旋遍历的时候,已经遍历的数字不能再次遍历,所以边界会越来越小。
规则是:如果当前行(列)遍历结束之后,就需要把这一行(列)的边界向内移动一格。
以下面的图为例, up, down, left, right 分别表示四个方向的边界,初始时分别指向矩阵的四个边界。如果我们把第一行遍历结束(遍历到了右边界),此时需要修改新的移动方向为向下、并且把上边界 up 下移一格,即从 旧 up 位置移动到 新 up 位置。
当绕了一圈后,从下向上走到 新up 边界的时候,此时需要修改新的移动方向为向右、并且把左边界 left 下移一格,即从 旧 left 位置移动到 新 left 位置。
由此可见,根据维护的四个方向的边界,就知道什么时候更改移动方向了。
3.4. 结束条件
螺旋遍历的结束条件是所有的位置都被遍历到。
4.代码:
Python
class Solution(object):
#定义一个名为Solution的类。
def spiralOrder(self, matrix):#定义一个名为spiralOrder的函数它有两个参数self和matrix
#matrix:二维列表
#self:类的实例本身
if not matrix or not matrix[0]: return []
#如果matrix为空或matrix的第一行为空,则返回一个空列表。
M, N = len(matrix), len(matrix[0])
#获取matrix的行数和列数,分别赋值给M和N
left, right, up, down = 0, N - 1, 0, M - 1
#初始化四个变量left、right、up和down,分别表示矩阵的左、右、上、下四个边界
res = []
#初始化空列表,用于存储矩阵中的元素
x, y = 0, 0
#初始两个变量x,y 用于表示当前起始位置
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 定义四个方向
cur_d = 0 # 初始方向为向右
while len(res) != M * N: # 当res中的元素数量等于矩阵中的元素数量时结束循环
res.append(matrix[x][y]) # 将当前位置的元素添加到res中
if cur_d == 0 and y == right: # 如果当前方向为向右且到达了右边界
cur_d += 1 # 改变方向为向下
up += 1 # 上边界向下移动一行
elif cur_d == 1 and x == down: # 如果当前方向为向下且到达了下边界
cur_d += 1 # 改变方向为向左
right -= 1 # 右边界向左移动一列
elif cur_d == 2 and y == left: # 如果当前方向为向左且到达了左边界
cur_d += 1 # 改变方向为向上
down -= 1 # 下边界向上移动一行
elif cur_d == 3 and x == up: # 如果当前方向为向上且到达了上边界
cur_d += 1 # 改变方向为向右
left += 1 # 左边界向右移动一列
cur_d %= 4#将cur_d的值限制在0到3之间,因为dirs列表中只有四个方向。
x += dirs[cur_d][0]
y += dirs[cur_d][1]
#根据当前方向更新当前位置。具体来说,dirs[cur_d][0]和dirs[cur_d][1]分别表示当前方向的行和列的偏移量,将它们加到x和y上即可得到下一个位置的坐标。
return res#最后,函数返回存储矩阵元素的列表res。