LeetCode 498. 对角线遍历【c++/java详细题解】

x33g5p2x  于2021-09-20 转载在 C/C++  
字(1.9k)|赞(0)|评价(0)|浏览(301)

1、题目

给定一个含有 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 。

2、思路

**(模拟)**O ( n ∗ m ) O(n/*m)O(n∗m)

我们能够想到的最为直接的思路就是:按照题目要求,模拟在数组中的行走路线,然后以对角线遍历的顺序返回这个矩阵中的所有元素。

首先来了解对角线的几个性质:

观察整个矩阵,我们可以发现,第一行的每一个元素对应一条对角线,最后一列的每一个元素对应一条对角线,两者重复包含右上角那条对角线。因此,假设矩阵的行数为n,列数为m,那么对角线的总数为: n + m - 1 。我们给每条对角线编个序号,如下图所示:

最左上角的为第0条对角线 ,最右下角的为第 n + m - 2条对角线。观察对角线的方向,注意到对角线的方向是向上或者向下交替进行的。 当对角线的序号是偶数时,对角线的方向向上;当对角线的序号是奇数时,对角线的方向向下。

矩阵行列的性质:

同一条对角线上的每个点(x, y)的横纵坐标之和 x + y相等,且都等于对角线的序号(仔细观察上图)。

如何确定每条对角线的起始和终点端点 ?

根据对角线性质,只要知道端点的横纵坐标之一,就可以得到另一维坐标,因此我们可以只关心横坐标。

对角线的起始和终点端点横坐标:

这样我们就确定了偶数对角线的起始和终点端点横坐标分别为x = min(i, n - 1)x = max(0, i - m + 1),纵坐标为i - x。(i是对角线序号)

而奇数对角线的遍历方向恰好和偶数对角线相反,因此奇数对角线的起始和终点端点横坐标分别为x = max(0, i - m + 1)x = min(i, n - 1),纵坐标为i - x。(i是对角线序号) 。

接下来的思路就很明确了,遍历每条对角线。如果是偶数对角线,就从下往上遍历;如果是奇数对角线,就从上往下遍历。

具体过程如下:

1、定义答案数组res,遍历每条对角线。
*
2、对于每条序号为i的对角线,判断其奇偶性:

如果是偶数对角线 ,确定其横坐标x,从下往上遍历,将mat[x][i - x]加入res中。
*
如果是奇数对角线 ,确定其横坐标x,从上往下遍历,将mat[x][i - x]加入res中。
*
3、最后返回res

**时间复杂度分析:**O ( n ∗ m ) O(n/*m)O(n∗m) ,每个元素只处理一遍。

3、c++代码

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<int> res;
        if (mat.empty() || mat[0].empty()) return res;
        int n = mat.size(), m = mat[0].size();
        for (int i = 0; i < n + m - 1; i ++ ) 
        {
            if (i % 2 == 0)  //偶数对角线
            {
                for (int x = min(i, n - 1); x >= max(0, i - m + 1); x -- )//从下往上遍历
                    res.push_back(mat[x][i - x]);
            } else 		     //奇数对角线
            {      
                for (int x = max(0,  i - m + 1); x <= min(i, n - 1); x ++ )//从上往下遍历
                    res.push_back(mat[x][i - x]);
            }
        }
        return res;
    }
};

4、java代码

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
    if (mat.length == 0 || mat[0].length == 0) return new int[0];
    int n = mat.length, m = mat[0].length;
    int[] res = new int[n * m];
    for (int i = 0, idx = 0; i < n + m - 1; i++) 
    {
        if (i % 2 == 0) //偶数对角线
            for (int x = Math.min(i, n - 1); x >= Math.max(0, i - m + 1); x -- ) //从下往上遍历
                res[idx++] = mat[x][i - x];
        else   		    //奇数对角线
            for (int x = Math.max(0, i - m + 1); x <= Math.min(i, n - 1); x ++ )//从上往下遍历
                res[idx++] = mat[x][i - x];
    }
    return res;
  }
}

原题链接:498. 对角线遍历

相关文章

微信公众号

最新文章

更多