夏天做那个网站能致富,上海在建工程查询,门户网站建设和推广,做产品代理上哪个网站好LeetCode 59.螺旋矩阵II
1、题目
力扣题目链接#xff1a;59. 螺旋矩阵 II - 力扣#xff08;LeetCode#xff09;
给你一个正整数 n #xff0c;生成一个包含 1 到 n2 所有元素#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1#xff1…
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:vectorvectorint generateMatrix(int n) {// 初始化一个n x n的二维数组所有元素初始化为0vectorvectorint res(n, vectorint(n, 0));// 定义螺旋矩阵的起始位置 (startx, starty)也可以理解为横纵坐标int startx 0, starty 0;// 循环的次数n 为奇数时中间会有一个单独的元素需要单独处理所以除以2int loop n / 2;// n为奇数时中间元素的坐标例如n为3 中间的位置就是(11)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)
