59. 螺旋矩阵 II

力扣链接(中等)：https://leetcode.cn/problems/spiral-matrix-ii

给你一个正整数 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

个人题解

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> resMatrix(n, vector<int>(n, 0));
        int startx = 0, starty = 0;     //循环起始位置
        int loop = n / 2;               //n * n的矩阵需要循环多少圈(中心位置除外)
        int mid = n / 2;                //中心位置
        int count = 1;                  //自增赋值数
        int offset = 1;                 //边长偏移量
        int i, j;

        while(loop --) {
            i = startx, j = starty;
            //左->右
            for(; j < n - offset; j ++ ) {
                resMatrix[startx][j] = count++;
            }
            //上->下
            for(; i < n - offset; i ++) {
                resMatrix[i][j] = count++;
            }
            //右->左
            for(; j > starty; j --) {
                resMatrix[i][j] = count++;
            }
            //下->上
            for(; i > startx; i --) {
                resMatrix[i][j] = count++;
            }
            //循环下一圈之前的处理
            //起始位置改变
            startx ++;
            starty ++;
            offset ++;
        }

        //处理中心位置
        if (n % 2) {
            resMatrix[mid][mid] = count;
        }
        return resMatrix;
    }
};

官方题解

按层模拟

可以将矩阵看成若干层，首先填入矩阵最外层的元素，其次填入矩阵次外层的元素，直到填入矩阵最内层的元素。

定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如，下图矩阵最外层元素都是第 1 层，次外层元素都是第 2 层，最内层元素都是第 3 层。

[[1, 1, 1, 1, 1, 1],
 [1, 2, 2, 2, 2, 1],
 [1, 2, 3, 3, 2, 1],
 [1, 2, 3, 3, 2, 1],
 [1, 2, 2, 2, 2, 1],
 [1, 1, 1, 1, 1, 1]]

对于每层，从左上方开始以顺时针的顺序填入所有元素。假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序填入当前层的元素。

从左到右填入上侧元素，依次为 (top,left) 到 (top,right)。

从上到下填入右侧元素，依次为 (top+1,right) 到 (bottom,right)。

如果 left<right 且 top<bottom，则从右到左填入下侧元素，依次为 (bottom,right−1) 到 (bottom,left+1)，以及从下到上填入左侧元素，依次为 (bottom,left) 到 (top+1,left)。

填完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续填入元素，直到填完所有元素为止。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int num = 1;
        vector<vector<int>> matrix(n, vector<int>(n));
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                matrix[top][column] = num;
                num++;
            }
            for (int row = top + 1; row <= bottom; row++) {
                matrix[row][right] = num;
                num++;
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    matrix[bottom][column] = num;
                    num++;
                }
                for (int row = bottom; row > top; row--) {
                    matrix[row][left] = num;
                    num++;
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return matrix;
    }
};

复杂度分析

• 时间复杂度：\(O(n^2 )\)，其中 n 是给定的正整数。矩阵的大小是 \(n×n\)，需要填入矩阵中的每个元素。

• 空间复杂度：\(O(1)\)。除了返回的矩阵以外，空间复杂度是常数。