【中等】59.螺旋矩阵Ⅱ

题目描述

给你一个正整数 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

解题方法

详细地解题方法看视频代码随想录

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

由外向内一圈一圈这么画下去。

这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。

这也是坚持了每条边左闭右开的原则。每一步都坚持这个规则。

代码如下：

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n, 0));  //使用vector定义一个二维数组int startx = 0, starty = 0; //定义每个圈的起始位置int loop = n / 2;   // 每个圈循环的次数，男，则loop=1只循环一圈int mid = n / 2;    // 矩阵的中间位置，n=3，中间位置为（1，1）int count = 1;     // 给矩阵中每个空格赋值int offset = 1;     // 控制每个边需要收缩的长度int i,j;while(loop--){i = startx;j = starty;// 开始模拟四个for 就是模拟转了一圈// 填充上行从左到右（左闭右开）for(j; j < n - offset; j++){res[i][j] = count++;}// 填充右列从上到下（左闭右开）for(i; i < n - offset; i++){res[i][j] = count++;}// 填充下行从右到左（左闭右开）for( ; j > starty; j--){res[i][j] = count++;}// 填充左列从下到上（左闭右开）for( ; i > startx; i--){res[i][j] = count++;}// 第二圈开始，起始位置各加1startx++;starty++;// offset控制每一边的长度offset++;}// 如果n为奇数，要单独给中间位置赋值if(n % 2){res[mid][mid] = count;}return res;}
};

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