[[模拟]]

螺旋矩阵

题目

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

n = 4

具体思路

• 设定每一轮的循环次数，循环起始位置，单层循环的长度。
• 按照四个方向的遍历顺序进行遍历。

具体代码

Java

class Solution {
    public int[][] generateMatrix(int n) {
        int startX = 0;
        int startY = 0;
        int loop = n / 2;
        int[][] res = new int[n][n];
        int offset = 1;
        int num = 1;
        if (n % 2 == 1) {
            res[n / 2][n / 2] = n * n;
        }
        int i = n;
        while (loop > 0) {
            loop--;
            int xRay = startX;
            int yRay = startY;
            i = n;
            while (i - offset - startX > 0) {
                res[xRay][yRay] = num++;
                yRay++;
                i--;
            }
            i = n;
            while (i - offset - startX > 0) {
                res[xRay][yRay] = num++;
                xRay++;
                i--;
            }
            i = n;
            while (i - offset - startX > 0) {
                res[xRay][yRay] = num++;
                yRay--;
                i--;
            }
            i = n;
            while (i - offset - startX > 0) {
                res[xRay][yRay] = num++;
                xRay--;
                i--;
            }
            startX++;
            startY++;
            offset++;
        }
        return res;
    }
}

CPP

[[include]] <iostream>
[[include]] <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, n * n));
        int startIndex = 0;
        int count = 1;
        int value = 1;
        int row = 0;
        int column = 0;
        int loop = n / 2;
        for (int t = 0; t < loop; t++) {
            // 从左到右
            for (; column < n - count; column++) {
                res[row][column] = value;
                value++;
            }

            // 从上到下
            for (; row < n - count; row++) {
                res[row][column] = value;
                value++;
            }

            // 从右到左
            for (; column > count - 1; column--) {
                res[row][column] = value;
                value++;
            }

            // 从下到上
            for (; row > count - 1; row--) {
                res[row][column] = value;
                value++;
            }

            // 更新下一轮起点
            count++;
            column++;
            row++;
        }
        return res;
    }
};

int main() {
    int n = 6;
    Solution s;
    vector<vector<int>> res = s.generateMatrix(n);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度: O(n^2)。生成矩阵需要遍历 n^2 个元素，每个元素都被访问一次。
• 空间复杂度: O(1)。除了返回结果矩阵外，使用的额外空间是常数级别的变量。