59. Spiral Matrix II

problem description

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

algorithm thought

和之前旋转矩阵题类似解答，可以移步到Spiral Matrix看algorithm thought

code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));
        vector<int> nstep{n,n-1};
        vector<vector<int>> move{{0,1},{1,0},{0,-1},{-1,0}};
        int i=0,j=-1;
        int pos=0;
        int tmp=1;
        while(nstep[pos%2]){
            for(int k=0;k<nstep[pos%2];++k){
                i+=move[pos%4][0];j+=move[pos%4][1];
                //cout<<i<<'-'<<j<<' ';
                res[i][j]=tmp++;
            }
            nstep[pos%2]--;
            pos++;   
        }
        return res;
    }
};

algorithm analysis

需要填满n*n个格子，每次填格子移动时间O(1)，最后时间复杂度O(n²)