【LeetCode】59. 螺旋矩阵 II
1 题目描述
给定一个正整数 n
,生成一个包含从 1 到 n^2
所有元素的 n x n
正方形矩阵 matrix
,并且这些元素按照顺时针方向螺旋排列。
2 解题思路
此题要求我们生成一个螺旋矩阵,我们可以考虑使用循环来逐层填充矩阵。对于每一层,我们需要依次处理四个边界:上边、右边、下边和左边。
具体来说,我们可以定义四个指针 startX
, startY
, offset
, 和 loop
,它们分别代表当前层的起始行坐标、起始列坐标、偏移量(即到下一层的距离)以及循环次数。随着每一轮循环的结束,这些指针需要更新,以便处理下一层。
- 初始化变量:
- 创建一个
n×n
的二维数组ans
用于存放结果。 - 设置
startX
和startY
分别为 0,offset
为 1,loop
为 1。 - 初始化
count
为 1,用于跟踪当前需要填充的值。
- 创建一个
- 循环处理每一层:
- 使用
while
循环处理n/2
层。 - 每一层处理四个边界:上、右、下、左。
- 使用
- 填充边界:
- 上边:固定行坐标,增加列坐标。
- 右边:固定列坐标,增加行坐标。
- 下边:固定行坐标,减少列坐标。
- 左边:固定列坐标,减少行坐标。
- 处理奇数情况:
- 如果
n
是奇数,则中心位置还需要单独处理。
- 如果
- 返回结果:
- 返回填充好的
ans
。
- 返回填充好的
3 Java 代码实现
class Solution {
public int[][] generateMatrix(int n) {
int[][] ans = new int[n][n];
int startX = 0;
int startY = 0;
int offset = 1;
int loop = 1;
int count = 1;
int i, j;
// 处理每一层
while (loop <= n / 2) {
// 上边
for (j = startY; j < n - offset; j++) {
ans[startX][j] = count++;
}
// 右边
for (i = startX; i < n - offset; i++) {
ans[i][j] = count++;
}
// 下边
for (; j > startX; j--) {
ans[i][j] = count++;
}
// 左边
for (; i > startY; i--) {
ans[i][startY] = count++;
}
// 更新起始坐标和偏移量
startX++;
startY++;
offset++;
loop++;
}
// 处理奇数层的中心
if (n % 2 == 1) {
ans[startX][startY] = count;
}
return ans;
}
}
- 时间复杂度: O(n^2),因为每个元素都被放置一次。
- 空间复杂度: O(n^2),用于存储结果矩阵。
4 注意事项
- 边界条件处理:当
n
为奇数时,需要特别处理中心点的填充。 - 循环次数:循环的次数是
n/2
,因为每次循环都会处理外圈的一层。 - 更新偏移量:随着循环的进行,需要不断更新偏移量
offset
和起始点startX
,startY
。