Leaky Cauldron
0%

顺时针打印矩阵

Posted on Edited on

题目: LeetCode # 29

LeetCode # 54 类似

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:

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

输出: 

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

示例 2:

输入:

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

输出: 

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

方法一：模拟坐标移动

取左上角和右下角两个位置, 分别移动

1
2
3
4
(r1  , c1) (r1, c1+1) ··· (r1  , c2)
   ···                    (r1+1, c2)
(r2-1, c1)                    ···
(r2  , c1) ··· (r2, c2-1) (r2  , c2)

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int row1 = 0, col1 = 0;
        int row2 = matrix.length - 1, col2 = matrix[0].length - 1;

        while (row1 <= row2 && col1 <= col2)
            result.addAll(getEdge(matrix, row1++, col1++, row2--, col2--));

        return result;
    }

    public List<Integer> getEdge(int[][] m, int row1, int col1, int row2, int col2) {
        List<Integer> tmpResult = new ArrayList<>();

        if (row1 == row2) {
            for (int i = col1; i <= col2; i++)
                tmpResult.add(m[row1][i]);
            return tmpResult;
        }

        if (col1 == col2) {
            for (int i = row1; i <= row2; i++)
                tmpResult.add(m[i][col1]);
            return tmpResult;
        }

        int curR = row1;
        int curC = col1;
        while (curC != col2) tmpResult.add(m[row1][curC++]);
        while (curR != row2) tmpResult.add(m[curR++][col2]);
        while (curC != col1) tmpResult.add(m[row2][curC--]);
        while (curR != row1) tmpResult.add(m[curR--][col1]);

        return tmpResult;
    }
}

Python

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:
    def spiralOrder(self, matrix: list) -> list:
        result = []
        if not matrix or len(matrix) == 0: return result
        row1, col1 = 0, 0
        row2, col2 = len(matrix) - 1, len(matrix[0]) - 1

        def get_edge(matrix: list) -> list:
            if row1 == row2:
                for i in range(col1, col2 + 1):
                    result.append(matrix[row1][i])
                return

            if col1 == col2:
                for i in range(row1, row2 + 1):
                    result.append(matrix[i][col1])
                return

            for i in range(col1, col2): result.append(matrix[row1][i])
            for i in range(row1, row2): result.append(matrix[i][col2])
            for i in range(col2, col1, -1): result.append(matrix[row2][i])
            for i in range(row2, row1, -1): result.append(matrix[i][col1])

        while (row1 <= row2 and col1 <= col2):
            get_edge(matrix)
            row1, col1, row2, col2 = row1 + 1, col1 + 1, row2 - 1, col2 - 1

        return result

Go

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
func spiralOrder(matrix [][]int) []int {
    var result []int
    if matrix == nil || len(matrix) == 0 {
        return result
    }
    row1, col1 := 0, 0
    row2, col2 := len(matrix) - 1, len(matrix[0]) - 1

    for row1 <= row2 && col1 <= col2 {
        result = append(result, getEdge(matrix, row1, col1, row2, col2)...)
        row1, col1, row2, col2 = row1 + 1, col1 + 1, row2 - 1, col2 - 1
    }

    return result
}

func getEdge(m [][]int, row1, col1, row2, col2 int) []int {
    var tmpResult []int
    if row1 == row2 {
        for i := col1; i <= col2; i++ {
            tmpResult = append(tmpResult, m[row1][i])
        }
        return tmpResult
    }
    if col1 == col2 {
        for i := row1; i <= row2; i++ {
            tmpResult = append(tmpResult, m[i][col1])
        }
        return tmpResult
    }

    for i := col1; i < col2; i++ {
        tmpResult = append(tmpResult, m[row1][i])
    }
    for i := row1; i < row2; i++ {
        tmpResult = append(tmpResult, m[i][col2])
    }
    for i := col2; i > col1; i-- {
        tmpResult = append(tmpResult, m[row2][i])
    }
    for i := row2; i > row1; i-- {
        tmpResult = append(tmpResult, m[i][col1])
    }

    return tmpResult
}

方法二：移动边界法

使用四个变量分别记录四个方向上的边界，每遍历完一条边则边界向中心移动一个单位。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int l = 0, r = matrix[0].length - 1;
        int t = 0, b = matrix.length - 1;

        while (l <= r && t <= b) {
            for (int i = l; i <= r; i++) result.add(matrix[t][i]);
            t++;
            for (int i = t; i <= b; i++) result.add(matrix[i][r]);
            r--;
            for (int i = r; i >= l && t <= b; i--) result.add(matrix[b][i]);
            b--;
            for (int i = b; i >= t && l <= r; i--) result.add(matrix[i][l]);
            l++;
        }

        return result;
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def spiralOrder(self, matrix: list) -> list:
        result = []
        if not matrix or len(matrix) == 0: return result
        l, r, t, b = 0, len(matrix[0]) - 1, 0, len(matrix) - 1

        while l <= r and t <= b:
            for i in range(l, r + 1): result.append(matrix[t][i])
            t += 1
            for i in range(t, b + 1): result.append(matrix[i][r])
            r -= 1
            if (l <= r and t <= b):
                for i in range(r, l - 1, -1): result.append(matrix[b][i])
                b -= 1
                for i in range(b, t - 1, -1): result.append(matrix[i][l])
                l += 1

        return result

利用 zip 函数：

1
2
3
4
5
6
7
8
class Solution:
    def spiralOrder(self, matrix: list) -> list:
        res = []
        while matrix:
            res.extend(matrix[0])
            matrix[:] = list(zip(*matrix[1:]))[::-1]
        
        return res

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func spiralOrder(matrix [][]int) []int {
    var result []int
    if matrix == nil || len(matrix) == 0 { return result }

    l, r, t, b := 0, len(matrix[0]) - 1, 0, len(matrix) - 1

    for l <= r && t <= b {
        for i := l; i <= r; i++ { result = append(result, matrix[t][i]) }
        t++
        for i := t; i <= b; i++ { result = append(result, matrix[i][r]) }
        r--
        for i := r; i >= l && t <= b; i-- { result = append(result, matrix[b][i]) }
        b--
        for i := b; i >= t && l <= r; i-- { result = append(result, matrix[i][l]) }
        l++
    }

    return result
}