Cinte's Leetcode Record
0%

54. Spiral Matrix

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

54. Spiral Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        int m = matrix.size();
        int n = matrix[0].size();
        int bL = 0, bR = n - 1, bU = 0, bB = m - 1;
        while(bL <= bR && bU <= bB)
        {
            for(int i = bL; i <= bR; ++i)
                ret.push_back(matrix[bU][i]);
            for(int i = bU + 1; i <= bB; ++i)
                ret.push_back(matrix[i][bR]);
            if(bU < bB && bL < bR)
            {
                for(int i = bR - 1; i > bL; --i)
                    ret.push_back(matrix[bB][i]);
                for(int i = bB; i > bU; --i)
                    ret.push_back(matrix[i][bL]);                
            }
            ++bL;
            --bR;
            ++bU;
            --bB;
        }
        return ret;
    }
};

螺旋

T(n) : O(n)
S(n) : O(n)

还有一种思路是把走过的路都设为障碍，每次要撞过去了就改变方向。不管如何，就是直接撞过去，撞到就变向，四个方向依次变 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.empty())
            return {};
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> visisted(n, vector<int>(m, 0));
        int d[4][4]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dr = 0;
        vector<int> ret;
        int i = 0, j = 0;
        while(1)
        {
            int nexti = i + d[dr][0];
            int nextj = j + d[dr][1];
            if(nexti < 0 || nextj < 0 || nexti >= n || nextj >= m || visisted[nexti][nextj])
                dr = (dr + 1) % 4;
            ret.push_back(matrix[i][j]);
            visisted[i][j] = 1;
            i += d[dr][0];
            j += d[dr][1];
            if(ret.size() == m * n)
                break;
        }
        return ret;
    }
};
T(n) : O(n)
S(n) : O(n * m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int dirs[][2]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int d = 0;
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = 0;
        vector<int> ret;
        ret.reserve(m * n);
        while(ret.size() < m * n)
        {
            ret.push_back(matrix[i][j]);
            matrix[i][j] = 101;
            int nextI = i + dirs[d][0];
            int nextJ = j + dirs[d][1];
            if(nextI < 0 || nextI >= m || nextJ < 0 || nextJ >= n || matrix[nextI][nextJ] == 101)
                d = (d + 1) % 4;
            i += dirs[d][0];
            j += dirs[d][1];
        }
        return ret;
    }
};