LeetCode_模拟_中等_498.对角线遍历

逃离我推掉我的手 2023-10-06 23:33 13阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**  
![在这里插入图片描述][2be3092088c046b48bcba631022ea7b6.png]  
输入：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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/diagonal-traverse

## 2.思路 ##

（1）模拟  
① 首先，分析题目可知，在整个遍历过程中，**只有两种遍历方向：右上方和左下方**；  
② 在朝**右上方遍历**时，如果遍历到边界（例如示例 1 中的元素 1 和 3）：此时先判断当前元素的**右侧相邻元素**的位置是否越界，如果未越界，则遍历该元素，并且**切换遍历方向**；如果越界，则选择当前元素的**下侧相邻元素**，同时也要切换遍历方向。  
③ 在朝**左下方遍历**时，其步骤与朝右上方遍历类似，此处不再赘述。  
④ 需要注意的是，由于在遍历过程中遍历方向有所不同，所以我们可能通过 boolean 变量 flag 来表示遍历方向，例如 flag = true 表示方向为右上方。此外，该方法的时间复杂度为 O(m \* n)。

## 3.代码实现（Java） ##

//思路1————模拟
    class Solution {
        
        public int[] findDiagonalOrder(int[][] mat) {
        
            // m 行 n 列的矩阵
            int m = mat.length;
            int n = mat[0].length;
            // res 保存最终的结果
            int[] res = new int[m * n];
            /*
                遍历方向只有两种：右上方和左下方
                刚开始的方向是右上方，将 flag 设置为 true
                那么 flag = false 表示方向为左下方
            */
            boolean flag = true;
            //从矩阵的左上角第一个元素开始遍历
            int i = 0, j = 0;
            //以对角线遍历方式开始遍历矩阵
            for (int k = 0; k < m * n; k++) {
        
                res[k] = mat[i][j];
                //右上方
                if (flag) {
        
                    //下一个元素的位置
                    int x = i - 1, y = j + 1;
                    //如果 x、y 超过了边界，则需要变换方向
                    if (x < 0 || y >= n) {
        
                        // (1) 下一个元素是右边相邻元素
                        x = i;
                        y = j + 1;
                        if (x < 0 || y >= n) {
        
                            // (2) 下一个元素是下边相邻元素
                            x = i + 1;
                            y = j;
                        }
                        //变换方向
                        flag = false;
                    }
                    // i、j 替代下一个元素的位置
                    i = x;
                    j = y;
                } else {
        
                    //左下方，这里的处理与右上方类似
                    int x = i + 1, y = j - 1;
                    //判断边界
                    if (x >= m || y < 0) {
        
                        x = i + 1;
                        y = j;
                        if (x >= m || y < 0) {
        
                            x = i;
                            y = j + 1;
                        }
                        //变换方向
                        flag = true;
                    }
                    i = x;
                    j = y;
                }
            }
            return res;
        }
    }

[2be3092088c046b48bcba631022ea7b6.png]: https://img-blog.csdnimg.cn/2be3092088c046b48bcba631022ea7b6.png