leetcode解题: Spiral Matrix (54)

发表于 | 分类于

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
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

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

解法1：O(M*N) Time, O(1) Space

运用分层处理的思想。一般情况，每一层有4条边组成，顺序是按照right, down, left, up。而且每一层的最后一行和第一行， 最后一列和第一列是对应关系。意思是说如果我们从第i行开始，那么与之对应的最后一行便是m - 1 - i, 列野同理。
那么层数有多少呢？这是又行数和列数决定的. level = (min(row, col) + 1) / 2
还有一个坑是对于单行或者单列的处理需要单独计算。

Java

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
40
41
42
43
44
45
46
47
public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        
        if (matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        
        int m = matrix.length, n = matrix[0].length;
        int level = (Math.min(m, n) + 1) / 2;
        
        for (int i = 0; i < level; ++i) {
            int lastrow = m - i - 1;
            int lastcol = n - i - 1;
            if (i == lastrow) {
                for (int j = i; j <= lastcol; ++j) {
                    res.add(matrix[i][j]);
                }
            } else if (i == lastcol) {
                for (int j = i; j <= lastrow; ++j) {
                    res.add(matrix[j][i]);
                }
            } else {
                // To right
                for (int j = i; j < lastcol; ++j) {
                    res.add(matrix[i][j]);
                }
                // down
                for (int j = i; j < lastrow; ++j) {
                    res.add(matrix[j][lastcol]);
                }
                // left
                for (int j = lastcol; j > i; --j) {
                    res.add(matrix[lastrow][j]);
                }
                // up
                for (int j = lastrow; j > i; --j) {
                    res.add(matrix[j][i]);
                }
            }
            
        }
        
        return res;
        
    }
}