题解 | #顺时针打印矩阵#

题目难度：较难
题意描述：顺时针输出二维矩阵 如图所示

算法设计
完成这题有几个问题
1.点的移动问题
2.移动方向问题
3.判断填完了所有数

1.点的移动问题
首先把当前填的数当成一个点，每次点只会上下左右移动一位，这种移动采用偏移量的形式会很简洁

int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//dx表示x方向的偏移量，dy表示y方向上的偏移量
//这时每次移动可以表示为从(x,y)到(x+dx[k],y+dy[k])

k=0表示(x,y+1)当前为向右
k=1表示(x+1,y)当前为向下
k=2表示(x,y-1)当前为向左
k=3表示(x-1,y)当前为向上
2.移动方向
上面解决了点的移动问题，下面考虑点移动的方向，因为是顺时针，所以方向顺序为（右，下，左，上）循环
什么时候改变方向呢？
1.到达了矩阵的边界

if(x<0||x>n||y<0||y>m)//n为行数，m为列数

2.当前方向的下一个已经填过了
预先定义bool型st数组记录那些点已经填过了

if(st[x][y])

如何简便的改变方向，上面的偏移量即可完成，将偏移量四个数分别表示成（右，下，左，上），移动点是(x,y)到(x+dx[k],y+dy[k])所以k=(k+1)%4即可。
3.
下面一个问题是如何判断填完了所有数，需要填的数共有行列个，所以填了行列个数即填完了所有数
下面给出代码

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int>ans;//记录答案
        int st[10][10]={0};//判断当前点有没有填过数
        int h=matrix.size(),l=matrix[0].size();//行数
        int num=matrix.size()*matrix[0].size();//列数
        int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//x,y方向上的偏移量
        int k=0,x=0,y=0;//k表示方向，(x,y)表示当前坐标
        for(int i=1;i<=num;i++)//总共需要填行*列个数
        {
            ans.push_back(matrix[x][y]);//(x,y)填上数
            st[x][y]=1;//记录这个点已经填过数了
            int aa=x+dx[k],b=y+dy[k];//
        if(aa>=h||aa<0||b<0||b>=l||st[aa][b])//判断是否需要改变方向
        k=(k+1)%4;
        x=x+dx[k],y=y+dy[k];
        }
        return ans;
    }
};

复杂度分析
时间复杂度：填(n*m)个数，每次移动O(1),所以时间复杂度O(nm)
空间复杂度：st数组记录当前数是否被填过，空间复杂度O(nm)