LeetCode 59.螺旋矩阵II

LeetCode 59.螺旋矩阵II

1、题目

力扣题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入： n = 3
输出： [[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入： n = 1
输出： [[1]]

提示：

• 1 <= n <= 20

2、模拟

思路

这道题的目的是生成一个按照螺旋顺序填充的二维矩阵。给定一个整数n，它创建一个 n x n 的矩阵，并从左上角开始，按照顺时针方向螺旋填充数字，从1开始，直到填充完整个矩阵（n^2）。
我们可以通过模拟法来顺时针画出螺旋矩阵：

• 填充上边界：从左到右
• 填充右边界：从上到下
• 填充下边界：从右到左
• 填充左边界：从下到上

由外而内填充矩阵。
在这里要注意边界条件，否则很容易蒙圈。
每一圈，我们都要画四条边，每条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
下面按照左闭右开的原则，来画一圈，大家看一下：

这里每一种颜色，都代表一条边，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。这也是坚持了每条边左闭右开的原则。

代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        // 初始化一个n x n的二维数组，所有元素初始化为0
        vector<vector<int>> res(n, vector<int>(n, 0));
        // 定义螺旋矩阵的起始位置 (startx, starty)，也可以理解为横纵坐标
        int startx = 0, starty = 0;
        // 循环的次数，n 为奇数时，中间会有一个单独的元素需要单独处理，所以除以2
        int loop = n / 2;
        // n为奇数时，中间元素的坐标，例如：n为3， 中间的位置就是(1，1)
        int mid = n / 2; 
        // 定义当前填充的数字，从 1 开始
        int count = 1; 
        // 定义每次圈数增加时的偏移量，每次循环右边界收缩一位
        int offset = 1;
        int i,j;

        // 开始螺旋填充，每填充完一圈，loop 减 1
        while (loop --) {
            // 当前圈的起始横坐标和纵坐标
            i = startx;
            j = starty;
    
            // 下面开始的四个for就是模拟转了一圈
            // 从左到右填充上边界(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 从上到下填充右边界(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 从右到左填充下边界(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 从下到上填充左边界(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }
    
            // 更新下一圈的起始位置，例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;
    
            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }
    
        // 如果 n 是奇数，则填充中心位置
        if (n % 2) {
            res[mid][mid] = count;
        }
        
        // 返回填充好的螺旋矩阵
        return res;
    }
};

复杂度分析

• 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
• 空间复杂度 O(1)