题目描述

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

样例

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

算法1

(模拟) $O(n^2)$

不断往矩阵里填数，如果碰到边界或者已经填过的格子就右转弯。

时间复杂度

一共$n^2$个数，所以复杂度是$O(n^2)$

参考文献

C++ 代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        vector<int> dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};

        for (int r = 0, c = 0, d = 0, num = 1; num <= n * n; ++num){
            res[r][c] = num;

            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n || res[nr][nc] != 0){
                d = (d + 1) % 4;
                nr = r + dr[d];
                nc = c + dc[d];
            }
            r = nr; c = nc;
        }

        return res;
    }
};