LeetCode 对角线遍历 [中等]
给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/diagonal-traverse/
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,4,7,5,3,6,8,9]
解释:
题目分析
解法1
1.前三行,最基本的判断还是要有的,避免多余循环
2.假设横为x,竖为y,此题求解换个思路相当于求x,y
3.沿对角线遍历,那必然是x--,y++(自上而下)或y--,x++(自下而上)
4.转弯处注意边界值判断
代码实现
public class LeetCode_01_FindDiagonalOrder {
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int[] diagonalOrder = findDiagonalOrder(matrix);
System.out.println(Arrays.toString(diagonalOrder));
}
public static int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return new int[]{};
}
if (matrix.length == 1) {
return matrix[0];
}
int size = matrix.length * matrix[0].length;
int[] res = new int[size];
int x = 0;
int y = 0;
//true 表示向右上角遍历 false表示向左下角遍历
boolean flag = true;
for (int i = 0; i < size; i++) {
res[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 res;
}
}