题解 | #螺旋矩阵#

NC38 螺旋矩阵

题意分析：

以顺时针螺旋方式打印出矩阵所有的元素

题解一（模拟法）：

以螺旋的方式进行遍历矩阵。

使用深度优先搜索，初始时，我们向右搜索，到达边界或者下一个元素已经访问过了，就转变搜索方向。搜索方向的顺序为向右，向下，向左，向右。我们定义一个方向向量vector<pair<int,int>>direct = {{0,1},{1,0},{0,-1}, {-1,0}};，用于转变方向

代码实现如下：过程写在代码注释里

vector<pair<int, int>> direct = {{0,  1},
                                 {1,  0},
                                 {0,  -1},
                                 {-1, 0}};

void dfs(int s, int t, vector<vector<int>> &matri, vector<vector<int>> &vis, vector<int> &ret, int &cyc) {
    int n = matri.size();
    int m = matri[0].size();
    //ret用于保存最后遍历的结果，当其大小等于m*n，遍历结束
    if (ret.size() == m * n)return;
    //如果当前访问的位置合法且没有被访问过，就可以加入到ret中
    if (s >= 0 && s < n && t >= 0 && t < m && vis[s][t] == 0) {
        ret.push_back(matri[s][t]);
        vis[s][t] = 1;
    }
    //检查下一步的位置需不需要转变方向
    //下一步位置合法且没有被访问过
    if (s + direct[cyc].first >= 0 && s + direct[cyc].first < n &&
        t + direct[cyc].second >= 0 && t + direct[cyc].second < m &&
        vis[s + direct[cyc].first][t + direct[cyc].second] == 0) {
        s = s + direct[cyc].first;
        t = t + direct[cyc].second;
    } else {
        cyc = (cyc + 1) % 4;
    }
    dfs(s, t, matri, vis, ret, cyc);
}

vector<int> spiralOrder(vector<vector<int>> &matrix) {
    if(matrix.empty()) return {};
    int n = matrix.size();
    int m = matrix[0].size();

    vector<vector<int>> vis(n, vector<int>(m, 0));
    vector<int> ret;
    int cyc = 0;
    dfs(0, 0, matrix, vis, ret, cyc);
    return ret;
}

时间复杂度：，对矩阵所有元素遍历了一遍

空间复杂度：，申请了大小为m*n的vis矩阵用于标记矩阵是否被访问过了。

题解二（按层遍历）：

这里的螺旋遍历也可以看做是顺时针访问每一层，先访问最外层，然后访问内层，依次递推。

对于每一层，从左上方以顺序遍历一层。假设当前层的左上角坐标为(left,top)，右下角坐标为(right,bottom)，每一层的遍历过程如下：

1. 从左上到右上遍历元素，从(left,top)到(right,top)，不包含(right,top)位置，
2. 从右上到右下遍历元素，从(right,top)到(right,bottom)，不包含(right,bottom)位置，
3. 从右下到左下遍历元素，从(right,bottom)到(left,bottom)，不包含(left,bottom)位置，
4. 从左下到左上遍历元素，从(left,bottom)到(left,top)，不包含(left,top)位置，
5. 结束一层的遍历，更新(left,top)和(right,bottom)，(left,top)和(right,bottom)，向里走一步，，(left,top)表现为同时增1，(right,bottom)表现为减1.
6. 以上过程适合某一层为方形，当某一层变为一行，或者一列，后者只剩一个元素了，我们单独拎出来遍历即可。

结束遍历：当(left,top)跑到(right,bottom)的右下，或者在同一行或者同一列的时候结束遍历，处理剩下的。

代码实现如下：

vector<int> spiralOrder(vector<vector<int>> &matrix) {
    if (matrix.empty()) return {};

    int m = matrix.size(), n = matrix[0].size();
    vector<int> ret;
    int left = 0, top = 0, right = n - 1, bottom = m - 1;
    while (left <right && top <bottom) {
        //按照四个方向，对一层进行遍历    
        //上方，从左到右
        for (int i = left; i < right; i++) {
            ret.push_back(matrix[top][i]);
        }
        //右方，从上到下
        for (int i = top; i < bottom; i++) {
            ret.push_back(matrix[i][right]);
        }
        //下方，从右到左
        for (int i = right; i > left; i--) {
            ret.push_back(matrix[bottom][i]);
        }
        //左方，从下到上
        for (int i = bottom; i > top; i--) {
            ret.push_back(matrix[i][left]);
        }
        left++;
        right--;
        top++;
        bottom--;
    }
    //当剩下的元素仅有一个
    if(left==right&top==bottom){
        ret.push_back(matrix[left][top]);
    }
    //当剩下的元素不能围成一个矩形，是一个条带的时候
    else if(top==bottom){
        for (int i = left; i <=right; i++) {
            ret.push_back(matrix[top][i]);
        }
    }
    else if(left==right){
        for (int i = top; i <= bottom; i++) {
            ret.push_back(matrix[i][right]);
        }
    }
    return ret;
}

时间复杂度：，我们自外向里对所有有元素进行了一次遍历，没有重复遍历任何元素，访问的元素个数为m*n。

空间复杂度：，没有申请额外的数组。