跳至主要內容

0498. 对角线遍历

ITCharge大约 2 分钟

0498. 对角线遍历open in new window

  • 标签:数组、矩阵、模拟
  • 难度:中等

题目链接

题目大意

描述:给定一个大小为 m×nm \times n 的矩阵 matmat

要求:以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。

说明

  • m==mat.lengthm == mat.length
  • n==mat[i].lengthn == mat[i].length
  • 1m,n1041 \le m, n \le 10^4
  • 1m×n1041 \le m \times n \le 10^4
  • 105mat[i][j]105-10^5 \le mat[i][j] \le 10^5

示例

  • 示例 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]

解题思路

思路 1:找规律 + 考虑边界问题

这道题的关键是「找规律」和「考虑边界问题」。

找规律:

  1. 当「行号 + 列号」为偶数时,遍历方向为从左下到右上。可以记为右上方向 (1,+1)(-1, +1),即行号减 11,列号加 11
  2. 当「行号 + 列号」为奇数时,遍历方向为从右上到左下。可以记为左下方向 (+1,1)(+1, -1),即行号加 11,列号减 11

边界情况:

  1. 向右上方向移动时:
    1. 如果在最后一列,则向下方移动,即 x += 1
    2. 如果在第一行,则向右方移动,即 y += 1
    3. 其余情况想右上方向移动,即 x -= 1y += 1
  2. 向左下方向移动时:
    1. 如果在最后一行,则向右方移动,即 y += 1
    2. 如果在第一列,则向下方移动,即 x += 1
    3. 其余情况向左下方向移动,即 x += 1y -= 1

思路 1:代码

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        rows = len(mat)
        cols = len(mat[0])
        count = rows * cols
        x, y = 0, 0
        ans = []

        for i in range(count):
            ans.append(mat[x][y])

            if (x + y) % 2 == 0:
                # 最后一列
                if y == cols - 1:
                    x += 1
                # 第一行
                elif x == 0:
                    y += 1
                # 右上方向
                else:
                    x -= 1
                    y += 1
            else:
                # 最后一行
                if x == rows - 1:
                    y += 1
                # 第一列
                elif y == 0:
                    x += 1
                # 左下方向
                else:
                    x += 1
                    y -= 1
        return ans

思路 1:复杂度分析

  • 时间复杂度O(m×n)O(m \times n)。其中 mmnn 分别为二维矩阵的行数、列数。
  • 空间复杂度O(m×n)O(m \times n)。如果算上答案数组的空间占用,则空间复杂度为 O(m×n)O(m \times n)。不算上则空间复杂度为 O(1)O(1)

参考资料