LeetCode 498 Diagonal Traverse

LeetCode

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Constraints:

m == mat.length n == mat[i].length
1 <= m, n <= 10<sup>4</sup> 1 <= m * n <= 10<sup>4</sup>
* -10<sup>5</sup> <= mat[i][j] <= 10<sup>5</sup>

题目大意：

按类对角线梅花间竹地遍历每个元素，输出最后结果

找规律解题思路：

边界条件很难找，而且每一层的结束点也和矩阵的长度或宽度有关。先找规律，可以看出

每层的所有元素下标和相等

正常从左到右从上到下遍历矩阵，用一个dict来每层的每一个数，可以看出这些数的顺序都是按题目要求的，只不过是正序或逆序，所以最后按照奇偶决定是否正序或逆序加入到结果

解题步骤：

1. 从左到右从上到下遍历矩阵，dict[i + j]来加入每层的每一个数
2. dict的key的范围容易得知，按照奇偶决定是否正序或逆序加入到结果

注意事项：

1. dict[i + j]来加入每层的每一个数
2. dict的key的最大值为len(mat) + len(mat[0]) - 1

Python代码：

def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
	groups = collections.defaultdict(list)
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			groups[i + j].append(mat[i][j])
	res = []
	for i in range(len(mat) + len(mat[0]) - 1):
		if i % 2 == 1:
			res.extend(groups[i])
		else:
			res.extend(groups[i][::-1])
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(nm)

---

按题意II解题思路：

Python代码：

def print_diagnals(matrix):
    if not matrix or not matrix[0]:
        return []
    res = []
    is_reversed = True
    # all diagnal starting from top row
    for col in range(len(matrix[0])):
        diag_row, diag_col = 0, col
        one_print = []
        while diag_row < len(matrix) and diag_col >= 0:
            one_print.append(matrix[diag_row][diag_col])
            diag_row += 1
            diag_col -= 1
        if is_reversed:
            res.extend(one_print[::-1])
        else:
            res.extend(one_print)
        is_reversed = not is_reversed
    # diagnal start rightmost columns
    for row in range(1, len(matrix)):
        diag_row, diag_col = row, len(matrix[0]) - 1
        one_print = []
        while diag_row < len(matrix) and diag_col >= 0:
            one_print.append(matrix[diag_row][diag_col])
            diag_row += 1
            diag_col -= 1
        if is_reversed:
            res.extend(one_print[::-1])
        else:
            res.extend(one_print)
        is_reversed = not is_reversed
    return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(1)