剑指 Offer 29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

普通算法

思路

按右、下、左、上依次通过for循环打印外围。
注意重复输出问题。

实现

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if(matrix.size()==0) return {};
    // if(matrix[0].size()==0) return matrix;
    int m=matrix.size(),n=matrix[0].size();
    int Beg=0,iRow=m-1,jCol=n-1;
    vector<int> ans(m*n,0);
    int cnt=0;
    while(cnt<m*n){
        for(int j=Beg;j<=jCol;j++){
            ans[cnt++]=matrix[Beg][j];
        }
        for(int i=Beg+1;i<=iRow;i++){
            ans[cnt++]=matrix[i][jCol];
        }
        if(cnt==m*n) break;          //避免重复输出
        for(int j=jCol-1;j>=Beg;j--){
            ans[cnt++]=matrix[iRow][j];
        }
        for(int i=iRow-1;i>Beg;i--){
            ans[cnt++]=matrix[i][Beg];
        }
        Beg++;
        jCol--;
        iRow--;
    }
    return ans;
}

复杂度分析

• 时间复杂度:
• 空间复杂度: ，输出答案所用空间

❤❤DFS

思路

根据题目，输出顺序为右下左上，且输出路径只有一条，故可通过DFS来输出该条路径。输出路径需要完成如下两步：

1. 判断下一步是否合法（是否在矩阵范围内，以及是否走过）
2. 将该步所对应的值输出，并继续走直到走完整个矩阵

   实现

   ```cpp vector> vis; //访问矩阵 vector> dir; //方向 int maxCnt; //总步数 void __DFS(const vector>& matrix,vector& path,int x,int y,int d,int len){ //若已走完整个矩阵，则退出递归
   if(len==maxCnt) return;

    if(__check(matrix,x,y)){
        vis[x][y]=1;
        path[len]=matrix[x][y];
        __DFS(matrix,path,x+dir[d][0],y+dir[d][1],d,len+1);
    }
    else{
        //该方向不合法，回退一步换个方向走
        x-=dir[d][0];
        y-=dir[d][1];
        d=(d+1)%4;
        __DFS(matrix,path,x+dir[d][0],y+dir[d][1],d,len);
    }

   } bool __check(const vector>& matrix,const int x,const int y){ //判断该步(x,y)是否合法 if(x>=0 && y>=0 && x<matrix.size() && y<matrix[0].size() && vis[x][y]==0) return true; else return false; }

vector spiralOrder(vector>& matrix) { if(matrix.size()==0) return {}; dir={{0,1},{1,0},{0,-1},{-1,0}}; maxCnt=matrix.size()*matrix[0].size(); vector path(maxCnt,0); vis.assign(matrix.size(),vector(matrix[0].size(),0)); __DFS(matrix,path,0,0,0,0); return path; } ```

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分