/
对角线遍历.java
70 lines (63 loc) · 1.72 KB
/
对角线遍历.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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package io.github.dunwu.algorithm.array;
// 【对角线遍历】
//
// 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。
//
// 示例:
//
// 输入:
// [
// [ 1, 2, 3 ],
// [ 4, 5, 6 ],
// [ 7, 8, 9 ]
// ]
//
// 输出: [1,2,4,7,5,3,6,8,9]
//
// 说明:
//
// 给定矩阵中的元素总数不会超过 100000 。
import org.junit.jupiter.api.Assertions;
/**
* @author Zhang Peng
* @since 2018-11-04
*/
public class 对角线遍历 {
public static void main(String[] args) {
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[] expected = { 1, 2, 4, 7, 5, 3, 6, 8, 9 };
Assertions.assertArrayEquals(expected, 对角线遍历.findDiagonalOrder(matrix));
}
public static int[] findDiagonalOrder(int[][] matrix) {
if (matrix.length == 0) {
return new int[0];
}
int x = 0, y = 0;
final int M = matrix.length;
final int N = matrix[0].length;
int[] arr = new int[M * N];
for (int i = 0; i < arr.length; i++) {
arr[i] = matrix[x][y];
if ((x + y) % 2 == 0) {
if (y == N - 1) {
x++;
} else if (x == 0) {
y++;
} else {
x--;
y++;
}
} else {
if (x == M - 1) {
y++;
} else if (y == 0) {
x++;
} else {
x++;
y--;
}
}
}
return arr;
}
}