题目链接：https://leetcode-cn.com/problems/spiral-matrix/

题目要求：

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

举例：

1
2
输入：[[1,2,3],[4,5,6],[7,8,9]]
返回：[1,2,3,6,9,8,7,4,5]
image-20220118182124918

首先遍历最外圈，然后将矩阵缩小一圈，递归进行。

要注意边界条件，即矩阵为空，或1行或只有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
递归方法
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m=len(matrix)
        if m==0 or len(matrix[0])==0:
            return []
        n=len(matrix[0])
        
        newlist=matrix[0]
        if m>1:

            for i in range(1,m):
                newlist.append(matrix[i][n-1])

            for j in range(n-2,-1,-1):
                newlist.append(matrix[m-1][j])
            if n>1:
                for i in range(n-2,0,-1):
                    newlist.append(matrix[i][0])
            
        M=[]
        for k in range(1,m-1):
            t=matrix[k][1:-1]
            M.append(t)

        return newlist+self.spiralOrder(M)
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
35
思路清晰方法:
    class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res=[]
        if len(matrix)==0:
            return []
        #定义四个边界点
        left=0
        right=len(matrix[0])-1
        top=0
        bottom=len(matrix)-1
        #在不超过边界的条件下，进行一轮循环
        while (top<bottom and left<right):
            for i in range(left,right):
                res.append(matrix[top][i])
            for i in range(top,bottom):
                res.append(matrix[i][right])
            for i in range(right,left,-1):
                res.append(matrix[bottom][i])
            for i in range(bottom,top,-1):
                res.append(matrix[i][left])
            left+=1
            top+=1
            right-=1
            bottom-=1
        
        #如果剩余1行或1列：left=0 right1
        if top==bottom:
            for i in range(left,right+1):
                res.append(matrix[top][i])
        elif left==right:
            for i in range(top,bottom+1):
                res.append(matrix[i][left])
        return res

撞墙法，即改变方向法：

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

        x=y=0                                     # 矩阵元素位置初始化
        res = []                                  # 初始化，存储遍历后的矩阵元素
        dx = [ 0, 1, 0,-1]                        # 方向：右，下，左，上
        dy = [ 1, 0,-1, 0]                        # 注：与通常平面坐标系 记号 不同
        di = 0                                    # 初始化方向变量
        visited = set()                           # 初始化集合，存储已走过的坐标
        m,n = len(matrix),len(matrix[0])          # 矩阵的行列 
                
        for i in range(m*n):                                     # 
            res.append(matrix[x][y])                             # 存储遍历矩阵过的元素
            visited.add((x,y))                                   # 存储遍历过的坐标
            tx,ty = x+dx[di],y+dy[di]                            # 先记录下一步坐标，用于判断下一步怎么走
            if 0<=tx<m and 0<=ty<n and (tx,ty) not in visited:   # 判断坐标是否需变向，且没有遍历过
                x,y = tx,ty                                       
            else:                                                
                di = (di+1)%4                                    # 改变方向，右下左上为一圈，防止方向坐标越界
                x,y = x + dx[di],y+dy[di]                        # 下一步坐标
        return res
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
class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix or not matrix[0]: return []
        M, N = len(matrix), len(matrix[0])
        left, right, up, down = 0, N - 1, 0, M - 1
        res = []
        x, y = 0, 0
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        cur_d = 0
        while len(res) != M * N:
            res.append(matrix[x][y])
            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
            x += dirs[cur_d][0]
            y += dirs[cur_d][1]
        return res

大神版：

1
2
3
4
5
6
7
8
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            # 削头（第一层）
            res += matrix.pop(0)
            # 将剩下的逆时针转九十度，等待下次被削
            matrix = list(zip(*matrix))[::-1]
        return res