侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【模拟】对角线遍历

GabrielxD
2022-06-14 / 0 评论 / 0 点赞 / 184 阅读 / 641 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

498. 对角线遍历


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

示例 1:

image-20220614130923713

输入: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 <= 10^4
  • 1 <= m * n <= 10^4
  • -10^5 <= mat[i][j] <= 10^5

解题

方法一:模拟

思路

根据题意直接模拟,在奇数对角线从左下向右上遍历,偶数对角线从右上向左下遍历。

维护一个布尔值为 true 表示当前是奇数对角线,为 false 时表示当前是偶数对角线,在每次走到边界进入下一条对角线时切换状态。

image-20220614133145119

由该图可知:

  • 奇数对角线:
    • 正常情况下: x-- y++
    • 边界情况1: x==0y++
    • 边界情况2: y==n-1x++
  • 偶数对角线:
    • 正常情况下: x++ y--
    • 边界情况1: y==0x++
    • 边界情况2: x==m-1y++

而在矩阵是正方形时遍历正方形对角线的这一趟会出现两种边界情况同时成立的情况,这时候就需要决定判断的先后顺序了。

image-20220614134118862

如图可以很明显的看出来。

代码

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] ans = new int[m * n];
        int x = 0, y = 0;
        boolean flag = true;
        for (int i = 0; i < m * n; i++) {
            ans[i] = mat[x][y];
            if (flag) {
                if (y + 1 == n) {
                    x++;
                    flag = !flag;
                } else if (x == 0) {
                    y++;
                    flag = !flag;
                } else {
                    x--;
                    y++;
                }
            } else {
                if (x + 1 == m) {
                    y++;
                    flag = !flag;
                } else if (y == 0) {
                    x++;
                    flag = !flag;
                } else {
                    x++;
                    y--;
                }
            }
        }
        return ans;
    }
}

另一种方法判断对角线状态:

找规律我们会发现:

对角线1   (0, 0)                 x + y = 0
对角线2   (0, 1) (1, 0)          x + y = 1
对角线3   (2, 0) (1, 1) (0, 2)   x + y = 2
对角线4   (1, 2) (2, 1)          x + y = 3
对角线5   (2, 2)                 x + y = 4

我们可以很明显的发现横纵坐标相加为偶数时是↗遍历,为奇数时是↙遍历。

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] ans = new int[m * n];
        int x = 0, y = 0;
        for (int i = 0; i < m * n; i++) {
            ans[i] = mat[x][y];
            if (((x + y) & 1) == 0) {
                if (y + 1 == n) x++;
                else if (x == 0) y++;
                else {
                    x--;
                    y++;
                }
            } else {
                if (x + 1 == m) y++;
                else if (y == 0) x++;
                else {
                    x++;
                    y--;
                }
            }
        }
        return ans;
    }
}
0

评论区