题目描述
给你一个正整数 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
解题方法
模拟
这道题和第48题相似,都是模拟螺旋矩阵的遍历方式。那我们怎么遍历呢?
我说一下具体思路,我们可以设置四个点,sr
在左上角,er
在右上角,sc
在左下角,ec
在右下角。每次遍历时,我们先从sr
往右遍历到er
,再由er
往下遍历到ec
,再由ec
往左遍历到sc
,再由sc
往上遍历到sr
。遍历完一圈后,我们再把sr
、er
、sc
、ec
往内缩一格,然后按照上面的方式继续遍历。直到sr
、er
、sc
、ec
缩到最内层时,遍历完成。同时我们在遍历的过程中给每个位置赋值。
java代码
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
// 起始行
int sr = 0;
// 起始列
int sc = 0;
// 结束行
int er = n - 1;
// 结束列
int ec = n - 1;
int num = 1;
while (sr <= er && sc <= ec) {
// 起始行、起始列、结束行、结束列在同一位置,只剩最后一个元素
if (sr == er && sc == ec) {
matrix[sr][sc] = num++;
break;
}
// 其余情况,按照右、下、左、上的顺序遍历
for (int i = sc; i < ec; i++) {
matrix[sr][i] = num++;
}
for (int i = sr; i < er; i++) {
matrix[i][ec] = num++;
}
for (int i = ec; i > sc; i--) {
matrix[er][i] = num++;
}
for (int i = er; i > sr; i--) {
matrix[i][sc] = num++;
}
// 每遍历完一圈,起始行、起始列、结束行、结束列往内缩一格
sr++;
sc++;
er--;
ec--;
}
return matrix;
}
复杂度分析
时间复杂度: O ( N ) O(N) O(N),需要遍历一次矩阵。
空间复杂度: O ( 1 ) O(1) O(1),只有几个变量存储。
相似题目
[leetcode] 48. 旋转图像
[leetcode] 54. 螺旋矩阵
- 个人公众号
- 个人小游戏