将矩阵按对角线排序

标签: 数组 矩阵 排序

难度: Medium

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。

给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。

 

示例 1：

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

示例 2：

输入：mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
输出：[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

 

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • 1 <= mat[i][j] <= 100

Submission

运行时间: 28 ms

内存: 16.3 MB

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        def helpSort(startI: int, startJ: int):
            l = []
            i, j = startI, startJ
            while i < m and j < n:
                l.append(mat[i][j])
                i += 1
                j += 1
            l.sort()
            for k in range(len(l)):
                mat[startI + k][startJ + k] = l[k]
        for i in range(n):
            helpSort(0, i)
        for i in range(1, m):
            helpSort(i, 0)
        return mat

Explain

该题解通过对每个对角线上的元素进行收集、排序和重新放置来解决问题。首先，定义一个辅助函数 helpSort 来处理从特定起点 (startI, startJ) 开始的对角线元素。该函数首先遍历对应的对角线，收集所有元素到列表 l 中。然后对列表 l 进行排序，之后将排序后的元素重新赋值回矩阵的对应位置。对于矩阵的每个可能的对角线起点，分别调用 helpSort 函数。对角线的起点分两部分：一部分是矩阵的第一行每个元素作为起点，另一部分是矩阵的第一列除第一个元素外的每个元素作为起点。

时间复杂度: O((m + n) * min(m, n) * log(min(m, n)))

空间复杂度: O(min(m, n))

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        m = len(mat) # 矩阵的行数
        n = len(mat[0]) # 矩阵的列数
        def helpSort(startI: int, startJ: int):
            l = [] # 用于存储对角线元素的列表
            i, j = startI, startJ
            while i < m and j < n: # 收集对角线上的元素
                l.append(mat[i][j])
                i += 1
                j += 1
            l.sort() # 对收集的元素排序
            for k in range(len(l)): # 将排序后的元素放回矩阵
                mat[startI + k][startJ + k] = l[k]
        for i in range(n): # 对第一行的每个元素作为起点处理对角线
            helpSort(0, i)
        for i in range(1, m): # 对第一列的每个元素作为起点处理对角线
            helpSort(i, 0)
        return mat # 返回修改后的矩阵

Explore

在 helpSort 函数中，通过使用循环条件 `i < m` 和 `j < n` 确保了索引不会越界。这两个条件分别检查是否达到了矩阵的行边界和列边界，从而在对角线元素的收集过程中不会超出矩阵的实际大小。即使对角线的理论长度（从起点开始直到矩阵的一个角）可能大于矩阵的实际尺寸，这种检查确保了只有在索引有效时才会访问元素。

对角线上元素的起点是通过两个循环确定的：一个循环遍历矩阵的第一行的每个元素，另一个循环遍历矩阵的第一列的每个元素（除了第一个）。这样确保了从每个可能的起点开始处理对角线。对于矩阵的最后一行或最后一列，由于对角线始终从左上到右下方向延伸，所以起点不会位于最后一行或最后一列。因此，不需要特别处理这些边界条件，因为它们不会作为对角线的起点。

每个对角线的元素是独立处理的，因为对角线不会与其他对角线共享元素（除了在边界相交的点，此时这些点已经被定位且不再修改）。在 `helpSort` 函数中，每次都是对从特定起点开始的对角线元素进行收集、排序和重新放置。由于每个对角线处理完成后，其元素就固定下来，不会被后续对角线处理过程影响，因此可以确保一个对角线的排序不会干扰到其他对角线的元素排序。

虽然对角线在矩阵的边角处会相交，但每个对角线在处理时是独立的，且每个元素只会被排序一次。相交只发生在边角单个点，这些点在它们各自对角线的处理中已经被排序。因此，不存在重复排序的问题，因为每个对角线是从其特定的起点开始独立处理，且排序操作限定在该对角线的元素上。