题解 | #螺旋矩阵#

螺旋矩阵
题解一：递归
题解思路： 每次递归都剥离一层。
图示：

复杂度分析：
时间复杂度：,每个元素遍历一次
空间复杂度：,每一次递归完成，行列都会减2，所以是除2，加一的原因是向上取整，
实现如下：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
         if(matrix.size()==0) return {};
     int row = matrix.size();
     int col = matrix[0].size();
     vector<int> ans;
     spiral(ans,0,0,row-1,col-1,matrix);
     return ans;
    }
    void spiral(vector<int>&ans,int r,int l,int row,int col,vector<vector<int>>&matrix){
        if(r>row || l>col) return;
        if(r==row){// 最后中间一行
            for(int i =  l;i<=col;++i) ans.push_back(matrix[r][i]);  //
            return;
        }
        if(l == col){  //最后中间一列
            for(int i = r;i<=row;++i) ans.push_back(matrix[i][l]);
            return;
        }
        for(int i = l; i < col; i++) ans.push_back(matrix[r][i]);// 左-->右
        for(int i = r; i < row; i++) ans.push_back(matrix[i][col]); //上-->下
        for(int i = col; i > l; i--) ans.push_back(matrix[row][i]); //右--->左
        for(int i = row; i > r; i--) ans.push_back(matrix[i][l]);  //下-->上
        spiral(ans,r+1, l+1, row-1, col-1,matrix);
    }
};

题解二：模拟
题解思路：模拟螺旋矩阵的路径。开始从左上角，一层一层的遍历。
图示：

复杂度分析：
时间复杂度： ,每个元素都要遍历一边
空间复杂度：,除了要返回的数组，没有额外空间

实现如下：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        if(matrix.size()==0) return {};
        int row = matrix.size();
        int col = matrix[0].size();
        vector<int> res;
        // 输入的二维数组非法，返回空的数组
        if (row == 0 || col == 0)  return res;

        // 定义四个关键变量，表示左上和右下的打印范围
        int left = 0, top = 0, right = col - 1, bottom = row - 1;
        while (left <= right && top <= bottom)
        {
            // left to right
            for (int i = left; i <= right; ++i)  res.push_back(matrix[top][i]);
            // top to bottom
            for (int i = top + 1; i <= bottom; ++i)  res.push_back(matrix[i][right]);
            // right to left
            if (top != bottom)
            for (int i = right - 1; i >= left; --i)  res.push_back(matrix[bottom][i]);
            // bottom to top
            if (left != right)
            for (int i = bottom - 1; i > top; --i)  res.push_back(matrix[i][left]);
            left++,top++,right--,bottom--;   //往里一层
        }
        return res;
    }
};