題目

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

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

分析

這題思路挺簡單愧杯，將矩陣由外而內(nèi)分成若干層骑篙，每一層分成上下左右四個部分，依次遍歷即可盖腿。難點(diǎn)主要是麻煩以及容易出錯衅码，關(guān)鍵在于處理兩種邊界條件：

• m!=n 時如何處理時定续，如何處理最內(nèi)層（是一行或者一列）
• m==n但是為奇數(shù)時粥脚，如何處理最內(nèi)層（是一個數(shù)字）

具體的解法見代碼窃肠。

實(shí)現(xiàn)

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return {};
        vector<int> ans;
        int n = matrix.size();
        int m = matrix[0].size();
        int layers = (min(n,m)-1)/2;
        int x, y;
        for(int l=0; l<=layers; l++){
            int left = l;
            int right = m - l - 1;
            int top = l;
            int bottom = n - l - 1;
            x = top; y = left;
            while(y<=right){
                ans.push_back(matrix[x][y]);
                y++;
            }
            y = right; x++;
            while(x<=bottom){
                ans.push_back(matrix[x][y]);
                x++;
            }
            if(bottom>top){
                x = bottom; y--;
                while(y>=left){
                    ans.push_back(matrix[x][y]);
                    y--;
                }
            }
            if(left<right){
                y = left; x--;
                while(x>top){
                    ans.push_back(matrix[x][y]);
                    x--;
                }
            }
        }
        return ans;
    }
};

思考

看了別人的解法，發(fā)現(xiàn)另一種思路也很好刷允，而且感覺其結(jié)構(gòu)更加高級铭拧。貼出來欣賞下：

class Solution {
public:
    vector<vector<int> > visit;
    vector<int> res;
    int add_x[4] = {0, 1, 0, -1};
    int add_y[4] = {1, 0, -1, 0};
    int d = 0;
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (!m) return vector<int>();
        int n = matrix[0].size();
        visit = vector<vector<int> >(m, vector<int>(n, 0));
        helper(matrix, 0, 0);
        return res;
    }
    void helper(vector<vector<int> >& matrix, int x, int y) {
        visit[x][y] = 1;
        res.push_back(matrix[x][y]);
        int m = matrix.size();
        int n = matrix[0].size();
        if (x + add_x[d] >= m || y + add_y[d] >= n || x + add_x[d] < 0 || y + add_y[d] < 0 || visit[x + add_x[d]][y + add_y[d]]) {
            ++d;
            d %= 4;
        }
        if (x + add_x[d] >= m || y + add_y[d] >= n || x + add_x[d] < 0 || y + add_y[d] < 0 || visit[x + add_x[d]][y + add_y[d]]) return;
        helper(matrix, x + add_x[d], y + add_y[d]);
    }
};