0498：对角线遍历（★）

2016-05-12 约 316 字预计阅读 1 分钟次阅读

力扣第 498 题

题目

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 10⁴
1 <= m * n <= 10⁴
-10⁵ <= mat[i][j] <= 10⁵

分析

#1

最简单的就是遍历矩阵，将元素添加到对应对角线的列表中。最后再将第偶数条对角线反转即可。

1
2
3
4
5
6
7
8
9


def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
	m, n = len(mat), len(mat[0]) 
	A = [[] for _ in range(m+n-1)]
	for i,j in product(range(m), range(n)):
		A[i+j].append(mat[i][j])
	res = []
	for i, sub in enumerate(A):
		res.extend(sub if i%2 else sub[::-1])
	return res

56 ms

#2

也可以直接按对角线遍历。注意边界范围，第偶数条对角线反着遍历。

解答

1
2
3
4
5
6
7


def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
	res, m, n = [], len(mat), len(mat[0])
	for k in range(m+n-1):
		l, r = max(0, k-n+1), min(k, m-1)
		span = range(l, r+1) if k%2 else range(r, l-1, -1)
		res.extend(mat[i][k-i] for i in span)
	return res

72 ms

目录

0498：对角线遍历（★）

题目

分析

#1

#2

解答