题目要求
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]
。
上述思路的代码如下:
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;
}