题目要求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,4,7,5,3,6,8,9]
|
思路和代码
其实这道题目不难，只要捋清楚一些边界的场景即可。自上而下遍历数组时，一定是自右往左移动的，因此下标移动的方向为[row, column]=>[row+1, column-1]。自上而下有两种边界场景，一个是到达了左边界，此时的移动方向变为[row, column]=>[row+1, column], 即上图中的4->7。另一个是遇到了下边界，此时的移动方向变为[row, column]=>[row, column+1]，即上图中的8->9。同理，自下而上遍历数组时，一定是自左往右移动的，因此下标的移动方向为[row, column]=>[row-1, column+1]。它同样有两个边界场景，一个是到达了右边界，此时的移动方向变为[row, column]=>[row+1, column]，还有一个场景是遇到上边界，此时的移动方向变为[row, column]=>[row, column+1]。
上述思路的代码如下：
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
| public int[] findDiagonalOrder(int[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) return new int[0];
int row = matrix.length;
int column = matrix[0].length;
int[] result = new int[row * column];
int rowIndex = 0;
int columnIndex = 0;
boolean up = true;
int index = 0;
while(index < result.length) {
result[index++] = matrix[rowIndex][columnIndex];
if(up) {
if(rowIndex > 0 && columnIndex < column-1) {
rowIndex--;
columnIndex++;
}else {
up = false;
if(columnIndex < column-1){
columnIndex++;
}else {
rowIndex++;
}
}
}else {
if(rowIndex < row-1 && columnIndex > 0) {
rowIndex++;
columnIndex--;
}else{
up = true;
if(rowIndex < row-1) {
rowIndex++;
}else {
columnIndex++;
}
}
}
}
return result;
}
|