0498. 对角线遍历

[utterances-bot]

0498. 对角线遍历

498. 对角线遍历 # 标签：数组、矩阵、模拟 难度：中等 题目大意 # 描述：给定一个大小为 m * n 的矩阵 mat 。 要求：以对角线遍历的顺序，用一个数组返回这个矩阵

https://algo.itcharge.cn/solutions/0400-0499/diagonal-traverse/

[Jiahao-LI-QD]

不需要方向管理的，我感觉更简单理解：

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
    m = len(mat)
    n = len(mat[0])
    res = []
    d = {}
    for i in range(0, m):
        for j in range(0, n):
            if i + j not in d:
                d[i + j] = [mat[i][j]]
            else:
                d[i + j].append(mat[i][j])
    
    for i in d:
        if i % 2 != 0:
            res.extend(d[i])
        else:
            res.extend(d[i][::-1])
        
    return res

[cathyliucx]

1 如果在最后一列，则向下方移动，即 x += 1。
2 如果在第一行，则向右方移动，即 y += 1。 Step1 和 Step2 相反的话报错。

[mixin-xin]

"其余情况想右上方向移动" 原文中有笔误“想（向）”

[JiafengLiao]

也可以把对角线数量算出来，再算上每个对角线的起点位置就容易点

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m = len(mat)
        n = len(mat[0])
        i=j=0
        res = []
        for diagonal in range(0, m+n):
            if diagonal%2==0:
                i = min(diagonal, m-1)
                j = diagonal-i

                while i >= 0 and j < n:
                    res.append(mat[i][j])
                    i -= 1
                    j += 1
            else:
                j = min(diagonal, n-1)
                i = diagonal -j

                while j >= 0 and i < m:
                    res.append(mat[i][j])
                    i += 1
                    j -= 1
        return res