【LeetCode】59. 螺旋矩阵 II

in #programming3 months ago

1 题目描述

给定一个正整数 n,生成一个包含从 1 到 n^2 所有元素的 n x n 正方形矩阵 matrix,并且这些元素按照顺时针方向螺旋排列。

2 解题思路

此题要求我们生成一个螺旋矩阵,我们可以考虑使用循环来逐层填充矩阵。对于每一层,我们需要依次处理四个边界:上边、右边、下边和左边。

具体来说,我们可以定义四个指针 startX, startY, offset, 和 loop,它们分别代表当前层的起始行坐标、起始列坐标、偏移量(即到下一层的距离)以及循环次数。随着每一轮循环的结束,这些指针需要更新,以便处理下一层。

  1. 初始化变量
    • 创建一个 n×n 的二维数组 ans 用于存放结果。
    • 设置 startXstartY 分别为 0,offset 为 1,loop 为 1。
    • 初始化 count 为 1,用于跟踪当前需要填充的值。
  2. 循环处理每一层
    • 使用 while 循环处理 n/2 层。
    • 每一层处理四个边界:上、右、下、左。
  3. 填充边界
    • 上边:固定行坐标,增加列坐标。
    • 右边:固定列坐标,增加行坐标。
    • 下边:固定行坐标,减少列坐标。
    • 左边:固定列坐标,减少行坐标。
  4. 处理奇数情况
    • 如果 n 是奇数,则中心位置还需要单独处理。
  5. 返回结果
    • 返回填充好的 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