54. 螺旋矩阵

题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例2：

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

---

题解：

模拟。

但写法还是有点技巧的。首先移动的方向是 右 下 左 上 ，不停的依次循环这 4 个循环，直到遍历完所有元素。

那么我们就要按照上述四个方向走，模拟下标的变化。

有两种写法：

第一种是手动模拟这个过程，稍微麻烦点，但好理解：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if ( !n ) return {};
        int m = matrix[0].size();
        if ( !m ) return {};
        int FLAG = 1008611;
        vector<int> ret(n * m);
        int sx = 0, sy = 0, k = 0;
        while ( k < m * n ) {
            while ( sy < m && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx][sy++] = FLAG;
            }
            ++sx, --sy;
            while ( sx < n && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx++][sy] = FLAG;
            }
            --sx, --sy;
            while ( sy >= 0 && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx][sy--] = FLAG;
            }
            --sx, ++sy;
            while ( sx >= 0 && matrix[sx][sy] != FLAG ) {
                ret[k++] = matrix[sx][sy];
                matrix[sx--][sy] = FLAG;
            }
            ++sx, ++sy;
        }
        return ret;
    }
};
/*
时间：0ms，击败：100.00%
内存：6.6MB，击败：95.50%
*/

第二种是使用一个方向变量 d 控制移动方向，使用两个数组记录对应方向上坐标的偏移量，只要保证 d 的改变和坐标偏移量一一对应即可。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if ( !n ) return {};
        int m = matrix[0].size();
        if ( !m ) return {};
        vector<int> dx{ 0, 1, 0, -1 };
        vector<int> dy{ 1, 0, -1, 0 };
        int FLAG = 1008611;
        vector<int> ret(n * m);
        int sx = 0, sy = 0, d = 0, tx, ty;
        for ( int i = 0; i < n * m; ++i ) {
            ret[i] = matrix[sx][sy];
            matrix[sx][sy] = FLAG;
            tx = sx + dx[d];
            ty = sy + dy[d];
            if ( tx < 0 || tx >= n || ty < 0 || ty >= m || matrix[tx][ty] == FLAG ) {
                d = (d + 1) % 4;
                tx = sx + dx[d];
                ty = sy + dy[d];
            }
            sx = tx;
            sy = ty;
        }
        return ret;
    }
};
/*
时间：0ms，击败：100.00%
内存：6.6MB，击败：98.10%
*/