题解 | #螺旋矩阵(二)#

螺旋矩阵(二)

http://www.nowcoder.com/practice/2c8078a728834e81a046fdefdea049aa

题意

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

限制:

边长不大于20

方法

模拟实现

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

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

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

值	i	j	方向	操作
1	0	0	右	右侧还可以写,继续向右
2	0	1	右	右侧还可以写,继续向右
3	0	2	右->下	右侧超出边界,切换到向下
4	1	2	下	下侧还可以写,继续向下
5	2	2	下->左	下侧超出边界,切换到向左
6	2	1	左	左侧还可一写,继续向左
7	2	0	左->上	左侧超出边界,切换到向上
8	1	0	上->右	上方有值,切换到向右
9	1	1	-	-

代码

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})$

数学计算坐标

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

分别是

$(0, 0)$ 向右写

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

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

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

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

本质上也是上面的写法,不同的是,初始值不再是1,左上角坐标也不再是 $(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;
    }
};