题解 | #对角线遍历矩阵#

题目分析

1. 题目给出我们一个大小为n*m的二维数组矩阵
2. 题目要求我们按照对角线的访问顺序访问二维数组，并且返回访问顺序的列表

方法一：分类讨论

• 实现思路
  • 由于对角线访问的时候存在两个方向，因此我们记录一个方向转换的标记，通过奇偶来确定当前应该遍历的方向，偶数代表从左下遍历到右上的方向，奇数代表从右上遍历到左下的方向
  • 由于不知道n和m的大小，我们可以将一个矩阵分为四部分进行讨论
  1. 访问左上三角形区域，即当前访问的任何元素mat[i][j]，都有i<=n, j<=m，此时可以确定的是每次新的方向开始的时候，奇数起点行值为0，偶数起点的列值为0
  2. 当矩阵m>n时，列比行长，则对于偶数情况，可以确定起点的行值为n-1，对于奇数情况，可以确定起点的行值为0
  3. 当矩阵n>m时，行比列长，则对于偶数情况，可以确定起点的列值为0，对于奇数情况，可以确定起点的列值为m-1
  4. 访问右下三角形区域，即当前访问的任何元素mat[i][j]，都有i>n, j>m，此时可以确定的是每次新方向开始的时候，奇数起点的列值为m-1，偶数起点的行值为n-1
  • 分类讨论确定起点后，根据方向和边界调整横纵坐标的值进行迭代访问即可

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param mat int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def diagonalOrder(self , mat: List[List[int]]) -> List[int]:
        # write code here
        n = len(mat)
        m = len(mat[0])
        res = []
        for idx in range(m+n-1):
            if idx < m and idx < n:            # 处理左上三角形区域
                x = idx
                y = 0
                while x >= 0:
                    if idx % 2 == 0:
                        res.append(mat[x][y])
                    else:
                        res.append(mat[y][x])
                    x -= 1
                    y += 1
            elif idx < m and idx >= n:        # 处理列比行长的情况
                if idx % 2 == 0:
                    x = n - 1
                    y = idx - (n-1)
                    while x >= 0:
                        res.append(mat[x][y])
                        x -= 1
                        y += 1
                else:
                    x = 0
                    y = idx
                    while x < n:
                        res.append(mat[x][y])
                        x += 1
                        y -= 1
            elif idx >= m and idx < n:        # 处理行比列长的情况
                if idx % 2 == 0:
                    x = idx
                    y = 0
                    while y < m:
                        res.append(mat[x][y])
                        x -= 1
                        y += 1
                else:
                    y = m - 1
                    x = idx - (m-1)
                    while y >= 0:
                        res.append(mat[x][y])
                        x += 1
                        y -= 1
            else:                                # 处理右下三角形区域
                if idx % 2 == 0:
                    x = n - 1
                    y = idx - (n - 1)
                    while y < m:
                        res.append(mat[x][y])
                        x -= 1
                        y += 1
                else:
                    x = idx - (m - 1)
                    y = m - 1
                    while x < n:
                        res.append(mat[x][y])
                        x += 1
                        y -= 1
        return res

复杂度分析

• 时间复杂度：$O(n\times m)O(n\times m)$，由于对整个矩阵遍历，因此时间代价为访问所有矩阵元素的代价
• 空间复杂度：$O(n\times m)O(n\times m)$，返回的列表空间存储了所有矩阵元素，因此也矩阵大小的空间开销

方法二：抽象规律

• 实现思路
  • 给出的虽然是n*m大小的矩阵，我们可以将任务视为在(n+m)*(n+m)大小的矩阵中，有一部分区域是合法的
  • 因此我们只需要关注迭代时标记值i奇偶数所指代的方向，和合法的边界即可
  • 比如对于奇数从右上到左下的方向，我们直接用变量k从0遍历到i+1结束，因此访问的节点应该是mat[k][i-k]，但是对于这个节点我们有两个要求
    • k<n，必须保证行数最远不越界
    • i-k<m，必须保证列数在合法范围之内
  • 因此代码可读性强，编写工作量较小，但是时间代价较大

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param mat int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def diagonalOrder(self , mat: List[List[int]]) -> List[int]:
        # write code here
        n = len(mat)
        m = len(mat[0])
        res = []
        for i in range(0, m + n - 1):
            if i&1:                            # 处理奇数的部分，从右上到左下
                for k in range(0, i+1):
                    if k >= n:
                        break
                    if i - k >= m:
                        continue
                    res.append(mat[k][i-k])
            else:                              # 处理偶数的部分，从左下到右上
                for k in range(0, i+1):
                    if k >= m:
                        break
                    if i - k >= n:
                        continue
                    res.append(mat[i-k][k])
        return res

复杂度分析

• 时间复杂度：$O((n+m)\times (n+m))O((n+m)\times (n+m))$，由于对整个矩阵进行扩展，因此时间代价为扩展后的时间代价
• 空间复杂度：$O(n\times m)O(n\times m)$，返回的列表空间存储了所有矩阵元素，因此也矩阵大小的空间开销

方法三：重新整理数据结构

• 实现思路

  • 我们按照顺序遍历访问给出的mat二维数组

  • 但是在ans新的数据结构中装填这些顺序访问的元素时，重新编排其位置，按照对角线顺序和逆序进行装填

  • 最后将ans中的对角线元素重新连接起来即可

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param mat int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def diagonalOrder(self , mat: List[List[int]]) -> List[int]:
        # write code here
        n = len(mat)
        m = len(mat[0])
        ans = [[] for _ in range(m + n - 1)]
        for i in range(n):
            for j in range(m):
                if (i + j) % 2 == 0:
                    # 逆序（左下到右上）
                    ans[i+j] = [mat[i][j]] + ans[i+j]
                else:
                    ans[i+j].append(mat[i][j])
        res = []
        for row in ans:
            res += row
        return res

复杂度分析

• 时间复杂度：$O(n\times m)O(n\times m)$，时间上遍历了整个二维矩阵
• 空间复杂度：$O(n\times m)O(n\times m)$，空间上申请了$ansans$数据结构作为额外辅助空间