【矩阵】对角线遍历

想要看更加舒服的排版、更加准时的推送
关注公众号“不太灵光的程序员”
每日八点有干货推送，微信随时解答你的疑问

498 对角线遍历 python3

矩阵 中等

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

示例:

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

解释:

from typing import List


# 68%
# 执行用时：236 ms
# 内存消耗：16.2 MB
class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return matrix
        m = len(matrix)
        n = len(matrix[0])
        ret = []
        r = c = 0
        for i in range(m*n):
            ret.append(matrix[r][c])
            # r + c是遍历的层数，偶数层向上遍历，奇数层向下遍历
            if (r+c) % 2 == 0:
                # 先判断是否到达右边界，到达右边界直接向下一格
                if c == n - 1:
                    r += 1
                # 再判断是否是上边界，是的话向右移动一格
                elif r == 0:
                    c += 1
                else:
                    # 否则向上和向右
                    r -= 1
                    c += 1
            else:
                # 先判断是否到达下边界，到达下边界直接向右一格
                if r == m - 1:
                    c += 1
                # 再判断是否是左边界，是的话向下移动一格
                elif c == 0:
                    r += 1
                # 否则向下和向左
                else:
                    r += 1
                    c -= 1

        return ret


# 91.7%
# 执行用时：224 ms
# 内存消耗：16.7 MB
class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return matrix
        dic = dict()
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                if i+j in dic:
                    dic[i + j].append(matrix[i][j])
                else:
                    dic[i + j] = [matrix[i][j]]

        # {0: [1], 1: [2, 4], 2: [3, 5, 7], 3: [6, 8], 4: [9]}
        res = []
        for i in range(m+n-1):
            if i % 2 == 0:
                res += dic[i][::-1]
            else:
                res += dic[i]
        return res


if __name__ == "__main__":
    s = Solution()
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    ret = s.findDiagonalOrder(matrix)
    print(ret)

推荐阅读：

• Pandas对海平面温度异常进行分析
• 机器学习中必须要会用的模块
• 这些基础题你能答上来几个？
• 还不知道怎么运行Python代码，快来撸代码
  

本文地址：https://blog.csdn.net/qq_23934063/article/details/107451971