Algorithm Practice
Search…
498 Diagonal Traverse
1. Question
Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.
Example:
1
Input:
2
3
[
4
[ 1, 2, 3 ],
5
[ 4, 5, 6 ],
6
[ 7, 8, 9 ]
7
]
8
9
Output:
10
[1,2,4,7,5,3,6,8,9]
11
12
Explanation:
Copied!
2. Implementation
1
class Solution {
2
public int[] findDiagonalOrder(int[][] matrix) {
3
if (matrix == null || matrix.length == 0) {
4
return new int[0];
5
}
6
7
int m = matrix.length, n = matrix[0].length;
8
int[] res = new int[m * n];
9
int row = 0, col = 0;
10
11
for (int i = 0; i < m * n; i++) {
12
res[i] = matrix[row][col];
13
// Moving up first
14
if ((row + col) % 2 == 0) {
15
if (col == n - 1) {
16
++row;
17
}
18
else if (row == 0) {
19
++col;
20
}
21
else {
22
--row;
23
++col;
24
}
25
}
26
else {
27
if (row == m - 1) {
28
++col;
29
}
30
else if (col == 0) {
31
++row;
32
}
33
else {
34
++row;
35
--col;
36
}
37
}
38
}
39
return res;
40
}
41
}
Copied!
3. Time & Space Complexity
时间复杂度O(mn), 空间复杂度O(mn)
Last modified 2yr ago