【LeeCode矩阵】498 对角线遍历
程序员文章站
2022-07-13 21:59:31
...
想要看更加舒服的排版、更加准时的推送
关注公众号“不太灵光的程序员”
每日八点有干货推送，微信随时解答你的疑问
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)