leetcode 498 对角线遍历
2022-06-16 本文已影响0人
碎念枫子
[leetcode]题号498: 对角线遍历
给你一个大小为 m x n
的矩阵 mat
,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。
示例 1
输入:mat = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,4,7,5,3,6,8,9]
示例 2:
输入:mat = [[1,2],[3,4]]
输出:[1,2,3,4]
提示:
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
-105 <= mat[i][j] <= 105
解题思路
我的思路就是把数组的下标当坐标,根据图示的箭头改变坐标,当坐标溢出的时候(跑出格子),把坐标回退,再根据情况去移动坐标找到箭头改变的下一次初始移动坐标。
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[] result = new int[m * n];
int column = 0;
int raw = 0;
//方向大于0的时候往上走,方向小于0的时候往下走
int direction = 1;
for (int i = 0; i < result.length; i++) {
result[i] = mat[column][raw];
//箭头往上的情况
if (direction > 0) {
//上移
column--;
raw++;
//没有到顶时,走出格子
if (raw >= n) {
//回退
column++;
raw--;
//往下找坐标
column++;
//方向改变
direction = -direction;
} else if (column < 0) {//到顶部的情况
//往下找坐标
column++;
//方向改变
direction = -direction;
}
}//箭头往下的时候
else {
//下移动
column++;
raw--;
//当移动到底部,走出格子
if (column >= m) {
//回退
column--;
raw++;
//往右边找坐标
raw++;
//方向改变
direction = -direction;
} else if (raw < 0) {//当移动到最左侧时
//往下找坐标
raw++;
//方向改变
direction = -direction;
}
}
}
return result;
}