498. 对角线遍历

Posted on | In
Words count in article: 376 | Reading time ≈ 1

题目

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

示例1：

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

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

说明：

给定矩阵中的元素总数不会超过 100000 。

解法：

解法一：

1.前三行，最基本的判断还是要有的，避免多余循环
2.假设横为x，竖为y，此题求解换个思路相当于求x，y
3.沿对角线遍历，那必然是x–，y++（自上而下）或y–，x++（自下而上）
4.转弯处注意边界值判断

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
public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null) return null;
        if (matrix.length == 0) return new int[]{};
        if (matrix.length == 1) return matrix[0];
        int size = matrix.length * matrix[0].length;
        int[] result = new int[size];
        int x = 0;
        int y = 0;
        //true代表向右上角遍历，false代表向左下角遍历
        boolean flag = true;
        for (int i = 0; i < size; i++) {
            result[i] = matrix[x][y];
            if (flag) {
                x--;
                y++;
                //边界值判断，调整顺序
                if (y > matrix[0].length - 1) {
                    y = matrix[0].length - 1;
                    x += 2;
                    flag = false;
                }
                //边界值判断，调整顺序
                if (x < 0) {
                    x = 0;
                    flag = false;
                }
            } else {
                x++;
                y--;
                //边界值判断，调整顺序
                if (x > matrix.length - 1) {
                    x = matrix.length - 1;
                    y += 2;
                    flag = true;
                }
                //边界值判断，调整顺序
                if (y < 0) {
                    y = 0;
                    flag = true;
                }
            }
        }
        return result;
    }

参考资料

LeetCode-对角线遍历-题解

0%