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