Leetcode java 对角线遍历

最新推荐文章于 2025-02-23 14:29:06 发布

心之所向丶7

最新推荐文章于 2025-02-23 14:29:06 发布

阅读量859

点赞数

分类专栏：刷题 java数据结构与算法

本文链接：https://blog.csdn.net/javaisnotgood/article/details/88911202

版权

刷题同时被 2 个专栏收录

27 篇文章

订阅专栏

java数据结构与算法

22 篇文章

订阅专栏

该博客介绍了一种解决LeetCode中矩阵对角线遍历问题的方法。通过观察矩阵，确定了两种遍历方向——左上到右下和右上到左下，并在遍历过程中处理坐标越界问题，当出现越界时改变遍历方向。文章提供了详细的思路解析和边界条件处理策略。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

示例:

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

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

解释:

说明:给定矩阵中的元素总数不会超过 100000 。

思路：

横坐标为raw ,边界为m，纵坐标为col，边界为n

1 通过观察我们可以看出这是两个方向的遍历，分别为左上、右下，左上遍历时坐标+（-1,1），右下遍历时坐标+（1，-1）。

2 遍历过程中会出现坐标越界的情况，越界时遍历方向改变，越界分为4种情况，第一种右上侧越界这种越界时坐标raw+=2,col=n-1,第二种左下测越界col+=2，raw=m-1,第三种右上顶部越界 raw=0,第四种左下左边越界col=0。

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix.length==0||matrix[0].length==0){
            return new int[0];
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[] new_array = new int[m*n];
        int[][] trans = {{-1,1},{1,-1}};
        int raw = 0;
        int col = 0;
        int k = 0;
        for(int i=0;i<new_array.length;i++){
            new_array[i] = matrix[raw][col];
            raw += trans[k][0];
            col += trans[k][1];
            
            if(col > n-1){
                col = n-1;
                raw += 2; 
                k = 1 - k;
            }
            if(raw > m-1){
                raw = m-1;
                col += 2;
                k = 1 - k;
            }
            if(col < 0){
                col = 0;
                k = 1 - k;
            }
            if(raw < 0){
                raw = 0;
                k = 1 - k;
            }
        }
        return new_array;
    }
}