LeetCode 498. 对角线遍历

网友投稿 624 2022-11-24

LeetCode 498. 对角线遍历

LeetCode 498. 对角线遍历

题目描述:

给你一个大小为 ​​m x n​​​ 的矩阵 ​​mat​​ ,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。

示例

输入:mat = [[1,2,3],[4,5,6],[7,8,9]]输出:[1,2,4,7,5,3,6,8,9]

思路:

一个矩阵,假设共有n行,m列,则其对角线(指的是​​/​​​这种方向的对角线,而不是​​\​​​)一共有n + m - 1条。假设对角线编号从0开始,则所有对角线的编号范围则是​​[0,n + m - 2]​​​,并且容易得到一个性质,编号为​​i​​​的对角线上的点,其横纵坐标之和等于​​i​​。

观察数据样例可知:编号​​i​​​为偶数的对角线,遍历方向是从左下到右上;编号​​i​​为奇数的对角线,遍历方向是从右上到左下。

从左下到右上,点的坐标的变化是,行数减1,列数加1。即​​x--​​​,​​y++​​

从右上到左下,点的坐标的变化是,行数加1,列数减1,。即​​x++​​​,​​y--​​

当一条对角线遍历完成后,我们需要找到下一个点作为起点,并翻转遍历方向。

找到下一个点作为起点,可以分情况讨论。

设当前遍历的对角线的编号为​​i​​

当方向是从左下到右上时

当​​i < m - 1​​​时,下一个起点的列,一定是​​i + 1​​​,即​​y = i + 1​​​,而行,可以直接根据根据对角线上所有点的横纵坐标是个常数,来算出来,即​​x = (i + 1) - y​​当​​i >= m - 1​​​时,下一个起点的列,只能到最后一列,即​​y = m - 1​​​,而​​x = (i + 1) - y​​

当方向是从右上到左下时

当​​i < n - 1​​​时,下一个起点的行,一定是​​i + 1​​​,即​​x = i + 1​​​,而​​y = (i + 1) - x​​当​​i >= n - 1​​​时,下一个起点的行,只到最后一行,即​​x = n - 1​​​,而​​y = (i + 1) - x​​

class Solution { // 重要性质: 同一条对角线上的点, 其[x,y]坐标的和是固定的 // 对角线条数, 总共 m + n - 1 条 // 第 i 条对角线上的坐标的和为 i // 和为偶数, 向右上角走 (x--, y++) // 和为奇数, 向左下角走 (x++, y--) public int[] findDiagonalOrder(int[][] mat) { int n = mat.length, m = mat[0].length; int[] ans = new int[n * m]; int k = 0; int x = 0, y = 0; for (int i = 0; i < n + m - 1; i++) { if ((i & 1) == 0) { // 把这条线走到头 while (x >= 0 && y < m) ans[k++] = mat[x--][y++]; if (i < m - 1) y = i + 1; else y = m - 1; x = i + 1 - y; } else { while (x < n && y >= 0) ans[k++] = mat[x++][y--]; if (i < n - 1) x = i + 1; else x = n - 1; y = i + 1 - x; } } return ans; }}

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:[NOIP2002 普及组] 过河卒
下一篇:oracle索引
相关文章

 发表评论

暂时没有评论,来抢沙发吧~