题意分析

  • 给出一个n行n列的矩阵，需要我们返回这个矩阵的螺旋序列。也就是从左上角开始顺时针进行遍历，从外面往里面遍历，知道遍历了所有的数字。每个位置的数字只能被遍历一遍。

图片说明

思路分析

  • 我们可以观察得到，这个遍历的序列是从外面逐渐往里面进行扩展的。也就是先遍历完最外面的一层，然后遍历倒数第二层，倒数第三层，直到遍历完所有的数字。那么，我们就可以从这里突破，我们按照顺序先往右边进行遍历，然后往下面进行遍历，然后往左边进行遍历，最后往上面进行遍历。利用一个while循环直到遍历到的数字超过矩阵的数字的个数。
  • 还有一个要注意的就是我们需要对每个位置进行哈希，判断这个位置是否被访问过。这里我使用的是unordered_map进行处理。

解法一

  • 这种写法是直接在一个while里面先进行四个方向的遍历，然后进入下一个循环，中途使用unordered_map进行初始化。
  • 代码如下
    • 需要遍历所有的数字，并且每个位置的数字都只要遍历一遍，所以时间复杂度为O(nm)
    • 在解决问题的时候只开了少数变量，空间复杂度为O(1) 
class Solution {
public:
    unordered_map<int,int> vis;  // 进行哈希存储每个位置，判断每个位置是否被访问过
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ans;
        int m=matrix.size();
        if(m==0){
            return ans;
        }
        int n=matrix[0].size();


        int sum=n*m;
        int cnt=0;
        int fx=0,fy=0; // 设置起始点
        while(cnt<sum){
            // 先尽可能往左边走
            while(fy<n&&!vis[fx*sum+fy]){
                vis[fx*sum+fy]=1;
                ans.push_back(matrix[fx][fy]);
                fy++;
                cnt++;
            }
            // 回退
            fy--;
            fx++;

            // 尽可能往下边走
            while(fx<m&&!vis[fx*sum+fy]){
                vis[fx*sum+fy]=1;
                ans.push_back(matrix[fx][fy]);
                fx++;
                cnt++;
            }

            // 回退
            fx--;
            fy--;

            // 尽可能往左边走
            while(fy>=0&&!vis[fx*sum+fy]){
                vis[fx*sum+fy]=1;
                ans.push_back(matrix[fx][fy]);
                fy--;
                cnt++;
            }

            // 回退
            fy++;
            fx--;

            // 尽可能往上面走
            while(fx>=0&&!vis[fx*sum+fy]){
                vis[fx*sum+fy]=1;
                ans.push_back(matrix[fx][fy]);
                fx--;
                cnt++;
            }
            fx++;
            fy++;

            // 结束了一个环
        }

        return ans;
    }
};

解法二

  • 这种写法和上面的写法有点不一样，我们发现，最开始的外面的一圈围的是0，然后我们遍历完最外面的那层之后，我们可以在遍历的时候就将这个数字置为0，然后我们就可以利用位置上面的数字是否为0判断是否需要转换方向了。

  • 代码如下

    • 需要遍历所有的数字，并且每个位置的数字都只要遍历一遍，所以时间复杂度为O(nm)
    • 在解决问题的时候只用了少数几个变量，空间复杂度为O(1) 
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ans;
        int m=matrix.size();
        int n=matrix[0].size();
        if(m==0){
            return ans;
        }
        int i=0,j=0;
        int ti=0,tj=1;
        // 从外卖呢往里面走，每循环一次，就将这一圈都更新为0
        for(int x=0;x<n*m;x++){
            ans.push_back(matrix[i][j]);
            matrix[i][j]=0; // 将这个位置置为0
            if(matrix[(i+ti)%m][(j+tj)%n]==0){
                // 将x和y的方向调换
                int tmpi=ti,tmpj=tj;
                ti=tmpj;tj=-tmpi;
            }

            // 准备执行一下圈的遍历
            i+=ti;
            j+=tj;
        }
        return ans;
    }
};