54. Spiral Matrix

problem description

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

algorithm thought

我对这个题其实一点都不陌生。大一第一个学习，算法设计课，就有这个题目。说实话，就用死方法肯定能做出来，只是很多冗余代码，很多条件判断。我记得我当时用4个bool变量确定行动方向。最后4个int定义行动的长度。我第一次做这个题好像也是这么做的。但是我第三次做题我觉得我不可能还用这中办法。于是我看了discuss，发现确实有很好地办法。用一个step定义当前行动的次数，step模4就能得出行动的当前方向。step模2就能得到是左右移动还是上下移动。左右移动一次，下一次左右移动就要减一。再定义一个移动的次数，保存能够左右移动和上下移动的次数。这种算法就省去了很多的条件判断

code

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<vector<int>> move{{0,1},{1,0},{0,-1},{-1,0}};
        int nr=matrix.size(); if(nr==0) return {};
        int nc=matrix[0].size(); if(nc==0) return {};
        vector<int> res(nr*nc);
        int pos=0;
        vector<int> nstep{nc,nr-1};
        int step=0;
        nr=0;nc=-1;
        while(nstep[step%2]){
            for(int i=0;i<nstep[step%2];++i){
                nr+=move[step%4][0];
                nc+=move[step%4][1];
                res[pos++]=matrix[nr][nc];
            }
            nstep[step%2]--;
            step++;
        }
        return res;
    }
};

algorithm thought

虽然差算法和好算法，时间复杂度都需要O(n²)。但是这次的算法省去了很多多余中间变量，和条件判断，能够提升程序运行的时间。