题目链接
https://leetcode-cn.com/problems/diagonal-traverse/
题目描述
给你一个大小为 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
行和 n
列,通过正方向遍历图可知总共的遍历次数为 $m + n - 1$ 次,其中到达拐点 $n - 1$ 之前,row
一直为 0
,列 col
递增,拐点之后,col
不变,row
开始递增。
在每次遍历时要沿着对角线的方向找到对角线上的所有元素,如果当前项为 $mat[row][col]$,则对角线的下一项为 $mat[row + 1][col - 1]$,直到边界。
通过上图不难看出,边界条件限制的其实是 row
和 col
的值,col
不能小于 0
,row
不能大于等于 m
。
当偶数列对角线所有项都遍历后保存,并对保存的列表进行翻转,再依次合并进最终的结果中就可以完成对角线遍历输出结果的顺序要求,实现代码如下:
const findDiagonalOrder = (mat) => {
const result = [];
const m = mat.length;
const n = mat[0].length;
const index = n - 1;
let row = 0;
let col = 0;
for (let i = 0; i < m + n - 1; i++) {
const diagonal = [];
const inflexed = i > index;
row = inflexed ? i - index : 0;
col = inflexed ? index : i;
while (row < m && col >= 0) {
diagonal.push(mat[row][col]);
row++;
col--;
}
if (i % 2 === 0) {
diagonal.reverse();
}
result.push(...diagonal);
}
return result;
}
复杂度分析:
- 时间复杂度:由于矩阵的每一个点都遍历到,并且不存在重复遍历,所以时间复杂度为 $O(m * n)$;
- 空间复杂度:由于存储对角线元素的个数最大为
m
和n
的最小值,空间复杂度为 $O(min(m, n))$。