Leetcode 1329:将矩阵按对角线排序(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1329:将矩阵按对角线排序(超详细的解法!!!)

in leetcode with 0 comment

给你一个 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]]

提示:

解题思路

这个问题的难点在于斜线上的点怎么表示?实际上这个问题在Leetcode 51:N皇后(最详细的解法!!!)中就碰到过,我们当时通过x-y表示y=-x上的点。这个问题同理,可以通过x-y表示同一个斜线上的点。然后对于所有同一个斜线上的点排序即可。

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        r, c = len(mat), len(mat[0])
        data = collections.defaultdict(list)
        
        for i in range(r):
            for j in range(c):
                data[i - j].append(mat[i][j])
        
        for i in data:
            data[i].sort() 
            
        for i in range(r):
            for j in range(c):
                mat[i][j] = data[i - j].pop(0)
        return mat

这里我们使用list存储数据,当然也可以使用最小堆。这种做法的空间复杂度是O(MN),可以将其优化到O(min(M,N))

每次考虑添加一个斜线方向的数,然后将其排序即可。如何遍历同一个斜线上的数呢?先遍历所有行i找到所有以i开始的斜行,再通过j遍历列,那么此时同一斜行上数的坐标就是[i+j,j]。接着遍历所以以列i开始的斜行,坐标通过[j,i+j]表示。

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        r, c = len(mat), len(mat[0])

        for i in range(r):
            t, k = [], min(r - i, c)
            for j in range(k):
                t.append(mat[i + j][j])
                
            t.sort()
            for j in range(k):
                mat[i + j][j] = t[j]
        
        for i in range(1, c):
            t, k = [], min(c - i, r)
            for j in range(k):
                t.append(mat[j][i + j])
            
            t.sort()
            for j in range(k):
                mat[j][i + j] = t[j]
        return mat

这个问题有一个最简洁的写法,就是采用冒泡排序。我们可以遍历每个斜线上的数,然后两两比较,那么最多只要比较len(mat)-1次即可。

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        r, c = len(mat), len(mat[0])
        for _ in range(r - 1):
            for i in range(r - 1):
                for j in range(c - 1):
                    if mat[i][j] > mat[i + 1][j + 1]:
                        mat[i][j], mat[i + 1][j + 1] = mat[i + 1][j + 1], mat[i][j]
        return mat

这么做时间复杂度较高,但空间复杂度最低。

reference:

https://leetcode.com/problems/sort-the-matrix-diagonally/discuss/489737/C%2B%2B-bubble-sort-clean-clear-and-easy

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses