【leetcode】54 Spiral Matrix

发表于 | 分类于 ，


描述

给定m×n个元素的矩阵（m行，n列），以螺旋顺序返回矩阵的所有元素。

样例

样例1

1
2
3
4
5
6
7
输入:
[
 [ 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
输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

思路

四个方向移动, 显然这个算法会浪费更多的内存，第二种方法可以直接锁定位置

代码

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
38
39
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.size() == 0){return vector<int>();}
        vector<int> result;
        vector<vector<int>> visited(matrix.size(),vector<int>(matrix[0].size(),0));
        int row = 0,col=0;
        int count = 1;
        int dir[4][2]={
            {0,1},// to right
            {1,0},// to down
            {0,-1},// to left
            {-1,0}  //to up
        };
        result.push_back(matrix[0][0]);
        visited[0][0] = 1;
        int current_dir = 0;
        while(count < matrix.size()*matrix[0].size()){
            cout<< row <<", "<< col<<endl;
            int temp_row = row;
            int temp_col = col;
            temp_row += dir[current_dir][0];
            temp_col += dir[current_dir][1];
            if(temp_row<0 || temp_row>=matrix.size() || temp_col<0 || temp_col>=matrix[0].size() 
                || visited[temp_row][temp_col] == 1 ){
                current_dir = (current_dir+1)%4;
            }
            else{
                row = temp_row;
                col = temp_col;
                count++;
                visited[row][col] = 1;
                result.push_back(matrix[row][col]);
            }
        }
        return result;
    }

};

参考代码

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
vector<int> spiralOrder(vector<vector<int> > &matrix) {
    vector <int> v;
    int row = matrix.size();
    if (row<=0) return v;
    int col = matrix[0].size();
    if (col<=0) return v;
    int r, c;
    for (r=0, c=0; r<(row+1)/2 && c<(col+1)/2; r++, c++){
        //top
        for(int i=c; i<col-c; i++){
            v.push_back(matrix[r][i]);
        }
        //right
        for(int i=r+1; i<row-r; i++){
            v.push_back(matrix[i][col-c-1]);
        }
        //bottom
        for(int i=col-c-2; row-r-1>r && i>=c; i--){
            v.push_back(matrix[row-r-1][i]);
        }
        //left
        for(int i=row-r-2; col-c-1>c && i>r; i--){
            v.push_back(matrix[i][c]);
        }
    }
    return v;
}

参考

原题链接