题意

输出边长为n的从外到内顺时针螺旋矩阵

限制:

边长不大于20

方法

模拟实现

考虑从1开始写,那么如果考虑书写的方向,则有4个方向, 右下左上.

注意到当一个方向不可再书写时,切换到下一个方向即可

以题目中样例数据 n=3为例

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > Matrix(int n) {
        // write code here
        vector<vector<int> > res(n,vector<int>(n,0));
        int i = 0; // 当前横坐标
        int j = 0; // 当前纵坐标
        int o = 0; // 方向
        int di[] = {0,1,0,-1}; // i 沿方向变化
        int dj[] = {1,0,-1,0}; // j 沿方向变化
        for(int k = 1;k<=n*n;k++){
            res[i][j] = k; // 写入值
            int newi = i+di[o]; // 下一个i
            int newj = j+dj[o]; // 下一个j
            if(newi >=n || newi < 0 || newj >=n || newj < 0 || res[newi][newj] != 0){ // 新坐标不合法
                o = (o+1)%4; // 切换方向
                newi = i+di[o]; // 下一个i
                newj = j+dj[o]; // 下一个j
            }
            i = newi;
            j = newj;
        }
        return res;
    }
};

复杂度分析

时间复杂度: 对于每个位置上操作为常数次代价,所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 主要消耗在结果矩阵的存储,所以空间复杂度为$O(n^2)O(n^2)$

数学计算坐标

对于n>1, 最外层一共需要写$4\cdot (n-1)4\backslash cdot(n-1)$个数

分别是

$(0,0)(0,0)$向右写

$(0,n-1)(0,n-1)$向下写

$(n-1,n-1)(n-1,n-1)$向左写

$(n-1,0)(n-1,0)$向上写

那么写完以后,内层实际上就是$n-2n-2$的矩形了.

本质上也是上面的写法,不同的是,初始值不再是1,左上角坐标也不再是$(0,0)(0,0)$

因此如果提供初始值,和左上角坐标,剩余的部分也是一样

代码

class Solution {
public:
    // 每次书写最外一圈
    void writeN(vector<vector<int> > &m,int n,int off/*左上角*/,int & v/* 起始值*/){
        if(n == 1){
            m[off][off] = v;
            return;
        }
        int i = off;
        int j = off;
        int di[] = {0,1,0,-1}; // i 沿方向变化
        int dj[] = {1,0,-1,0}; // j 沿方向变化
        for(int k = 0;k < 4;k++){ // 4个方向
            for(int o = 1;o<n;o++){ // 每个n-1次
                m[i][j] = v++;
                i+=di[k];
                j+=dj[k];
            }
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > Matrix(int n) {
        // write code here
        vector<vector<int> > res(n,vector<int>(n,0));
        int off = 0;
        int base = 1;
        while(n > 0){
            writeN(res,n,off,base);
            off+=1;
            n-=2; // 下一圈长度-2
        }
        return res;
    }
};

复杂度分析

时间复杂度: 对于每个位置,操作代价是常数次,所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 主要消耗在结果矩阵的存储,所以空间复杂度为$O(n^2)O(n^2)$