链接
https://leetcode-cn.com/problems/spiral-matrix-ii/
耗时
解题:7 min
题解:11 min
题意
给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
提示:
思路
和 【leetcode】54. 螺旋矩阵(spiral-matrix)(模拟)[中等] 的思路完全相同,两题的区别基本只有把 54 的输入变成的输出,然后矩阵还简化成了方阵,更简单了,在 54 的代码基础上改改就可以了。
设置一个变量从 1 加到
n
2
n^2
n2。对于这个变量来说:
从外向内一圈一圈往里走,把每一圈看成一个循环结,一圈包括 上、右、下、左 四个部分,分别遍历赋值,需要注意的是当只有一行或一列时,需要特殊判断一下只遍历 上 或 右 就可以了,再多遍历,位置平行的部分就重复了。还有第一部分要遍历整个一行,否则的话只有一个元素时就不会遍历它。
时间复杂度:
O
(
n
2
)
O(n^2)
O(n2)
AC代码
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> matrix(n, vector<int>(n, 0));
int cnt = (n+1)/2;
int num = 0;
for(int i = 0; i < cnt; ++i) {
for(int j = i; j <= n-i-1; ++j) {
matrix[i][j] = ++num;
}
for(int j = i+1; j <= n-i-1; ++j) {
matrix[j][n-i-1] = ++num;
}
if(n-2*i > 1) {
for(int j = n-i-2; j >= i; --j) {
matrix[n-i-1][j] = ++num;
}
for(int j = n-i-2; j > i; --j) {
matrix[j][i] = ++num;
}
}
}
return matrix;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)