runtime 0 ms, beats 100% of cpp submissions
O(mn) solution with explanation

tags: simulation

Spiral Matrix

📖 description

給定一個 2 維陣列 (不一定是方陣)，依照螺旋順序儲存成 1 維陣列。

ex.
    Input: 
        matrix = [[1,2,3],[4,5,6],[7,8,9]]

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

🧠 solution

依照題意模擬操作，分成 4 個動作，分別是依照邊界對上下左右讀取，維護邊界的同時也要維護一個當前狀態來區分動作。

⏳ time complexity

遍歷一次 2 維陣列，時間複雜度 O(mn) ，其中 m 、 n 表示陣列的長寬。
總時間複雜度 O(mn)

📝 code

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
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& m) {
        // 分別表示 左、右、上、下 的邊界
        int l = 0,r = m[0].size()-1,t = 0,d = m.size()-1;
        int state = 0;
        vector<int> ans;
        while(l<=r && t<=d){
            if(state == 0){     // 由左往右
                for(int i=l;i<=r;i++){
                    ans.emplace_back(m[t][i]);
                }
                t++;
            }
            else if(state == 1){     // 由上往下
                for(int i=t;i<=d;i++){
                    ans.emplace_back(m[i][r]);
                }
                r--;
            }
            else if(state == 2){    // 由右往左
                for(int i=r;i>=l;i--){
                    ans.emplace_back(m[d][i]);
                }
                d--;
            }
            else{                   // 由下往上
                for(int i=d;i>=t;i--){
                    ans.emplace_back(m[i][l]);
                }
                l++;
            }
            state = (state+1)%4;    // 循環動作
        }
        return ans;
    }
};