LeetCode 59. 螺旋矩阵 II

59. 螺旋矩阵 II

题目：给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
链接 https://leetcode.cn/problems/spiral-matrix-ii/

个人思路

1. 模拟
   这道题刚开始看到时想了一晚上该怎么打印，其实也想到了官解的模拟，但是代码不会写，甚至想到了设置一个标志，类似于旗帜那样，但也无从下手，然后看了解答后豁然开朗，但当时没有cv，也没有立刻开写，然后现在过了几天自己终于写出来了。这里有个问题，就是我在刚开始构建二维数组测试时，使用了ans = [[0]*n]*n
   结果发现修改某个值时，整列数字都会被修改，后来发现是list * n的原因, list * n是n个list的浅拷贝的连接，即每个list指向的内存空间的同一个位置。要构造二维数组需要用列表表达式[[0] * m for _ in range(n)]
   
   然后模拟的时候，我们在while num <= n * n 进行循环，在每个循环里面根据从左到右，从上到下，从右到左，从下到上的规律进行外圈模拟，逐渐到内圈，代码如下：这里边界加减有个规律就是当你填充完从左到右后，说明顶部已经填充完一行，那么顶部边界t就要+1，其他类似

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        ans = [[0] * n for _ in range(n)]
        # 左右上下的边界
        l,r,t,b = 0,n-1,0,n-1  
        num = 1
        while num <= n * n:
            # 左到右
            for i in range(l,r+1):
                ans[t][i] = num
                num += 1
            t += 1 
            # 上到下   
            for i in range(t,b+1):
                ans[i][r] = num
                num += 1
            r -= 1
            # 右到左
            for i in range(r,l-1,-1):
                ans[b][i] = num
                num += 1
            b -= 1
            # 下到上
            for i in range(b,t-1,-1):
                ans[i][l] = num
                num += 1
            l += 1
        return ans
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

复杂度分析

复杂度分析

时间复杂度：O(n^2)，其中 n 是给定的正整数。矩阵的大小是 n×n，需要填入矩阵中的每个元素。
空间复杂度：O(1)。除了返回的矩阵以外，空间复杂度是常数。

其他思路

1. 官解写法

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        matrix = [[0] * n for _ in range(n)]
        row, col, dirIdx = 0, 0, 0
        for i in range(n * n):
            matrix[row][col] = i + 1
            dx, dy = dirs[dirIdx]
            r, c = row + dx, col + dy
            if r < 0 or r >= n or c < 0 or c >= n or matrix[r][c] > 0:
                dirIdx = (dirIdx + 1) % 4   # 顺时针旋转至下一个方向
                dx, dy = dirs[dirIdx]
            row, col = row + dx, col + dy
        
        return matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 按层模拟

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]
        num = 1
        left, right, top, bottom = 0, n - 1, 0, n - 1

        while left <= right and top <= bottom:
            for col in range(left, right + 1):
                matrix[top][col] = num
                num += 1
            for row in range(top + 1, bottom + 1):
                matrix[row][right] = num
                num += 1
            if left < right and top < bottom:
                for col in range(right - 1, left, -1):
                    matrix[bottom][col] = num
                    num += 1
                for row in range(bottom, top, -1):
                    matrix[row][left] = num
                    num += 1
            left += 1
            right -= 1
            top += 1
            bottom -= 1

        return matrix
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

参考：

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/spiral-matrix-ii/solution/luo-xuan-ju-zhen-ii-by-leetcode-solution-f7fp/