Leetcode498. 对角线遍历

2021年8月15日 1064点热度 1人点赞 0条评论

题目描述

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

示例:

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

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

说明:

  1. 给定矩阵中的元素总数不会超过 100000 。

解题思路

这道题只需要模拟就可以了。这道题需要做的是三部分:一个是变向,一个是怎么对角移动坐标,最后一个是怎么处理边界条件。

先说变向问题,这个很好处理。首先用一个变量direction指示方向,1表示向右上角移动,0表示向左下角移动,然后变向的操作可以用direction = 1 - direction完成。

接下来就是对角移动。这个也很容易观察出规律:

右上角:

[row, col] -> [row - 1, col + 1]

newRow = row - 1;

newCol = col + 1;

左下角:

[row, col] -> [row + 1, col - 1]

newRow = row + 1;

newCol = col - 1;

然后就是最为麻烦的边界条件处理。

首先是进行边界条件处理的条件是对角移动后坐标超出数组范围:

newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols

在往右上角移动的时候,可能到达上面的边界(col < cols - 1)或者右边的边界(col == cols - 1)。对这个需要进行分别的处理。当到达上面的边界的时候,col += 1;当到达右边的边界的时候,row += 1

在往左下角移动的时候,可能到达下面的边界(row == rows - 1)或者左边的边界(row < rows - 1)。对这个也需要进行分别的处理。当到达下面的边界的时候,col += 1;当到达左边的边界的时候,row += 1

最后还需要考虑以下什么时候退出循环。经过观察,发现不满足下面条件的时候推出就可以:

row < rows && col < cols

将上面列出的综合起来,就可以得到相关的代码。

参考代码

vector<int> findDiagonalOrder(vector<vector<int>>& mat){
    if(mat.empty()) return {};

    int rows = mat.size();
    int cols = mat[0].size();
    int row = 0, col = 0;
    int direction = 1;
    vector<int> result;

    while(row < rows && col < cols){
        result.emplace_back(mat[row][col]);

        int newRow = row + (direction == 1 ? -1 : 1);
        int newCol = col + (direction == 1 ? 1 : -1);

        if(newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols){
            if(direction == 1){
                if(col < cols - 1){
                    col += 1;
                }
                else if(col == cols - 1){
                    row += 1;
                }
            }else{
                if(row < rows - 1){
                    row += 1;
                }
                else if(row == rows - 1){
                    col += 1;
                }
            }
            direction = 1 - direction;
        }else{
            row = newRow;
            col = newCol;
        }
    }
    return result;
}

复杂度分析

时间复杂度:$O(rows \cdot cols)$​

空间复杂度:$O(1)$​,不考虑输入输出所需要的空间​

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

您需要 登录 之后才可以评论