跳转至

3446. 按对角线进行矩阵排序

题目描述

给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

  • 左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
  • 右上角三角形 的对角线按 非递减顺序 排序。

 

示例 1：

输入： grid = [[1,7,3],[9,8,2],[4,5,6]]

输出： [[8,2,3],[9,6,7],[4,5,1]]

解释：

标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：

  • [1, 8, 6] 变为 [8, 6, 1]。
  • [9, 5] 和 [4] 保持不变。

标有蓝色箭头的对角线（右上角三角形）应按非递减顺序排序：

  • [7, 2] 变为 [2, 7]。
  • [3] 保持不变。

示例 2：

输入： grid = [[0,1],[1,2]]

输出： [[2,1],[1,0]]

解释：

标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。

示例 3：

输入： grid = [[1]]

输出： [[1]]

解释：

只有一个元素的对角线已经符合要求，因此无需修改。

 

提示：

  • grid.length == grid[i].length == n
  • 1 <= n <= 10
  • -105 <= grid[i][j] <= 105

解法

方法一：模拟 + 排序

我们可以按照题目描述的要求，模拟对角线的排序过程。

我们首先对左下角三角形的对角线进行排序，然后对右上角三角形的对角线进行排序。最后返回排序后的矩阵即可。

时间复杂度 \(O(n^2 \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是矩阵的大小。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        for k in range(n - 2, -1, -1):
            i, j = k, 0
            t = []
            while i < n and j < n:
                t.append(grid[i][j])
                i += 1
                j += 1
            t.sort()
            i, j = k, 0
            while i < n and j < n:
                grid[i][j] = t.pop()
                i += 1
                j += 1
        for k in range(n - 2, 0, -1):
            i, j = k, n - 1
            t = []
            while i >= 0 and j >= 0:
                t.append(grid[i][j])
                i -= 1
                j -= 1
            t.sort()
            i, j = k, n - 1
            while i >= 0 and j >= 0:
                grid[i][j] = t.pop()
                i -= 1
                j -= 1
        return grid

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[][] sortMatrix(int[][] grid) {
        int n = grid.length;
        for (int k = n - 2; k >= 0; --k) {
            int i = k, j = 0;
            List<Integer> t = new ArrayList<>();
            while (i < n && j < n) {
                t.add(grid[i++][j++]);
            }
            Collections.sort(t);
            for (int x : t) {
                grid[--i][--j] = x;
            }
        }
        for (int k = n - 2; k > 0; --k) {
            int i = k, j = n - 1;
            List<Integer> t = new ArrayList<>();
            while (i >= 0 && j >= 0) {
                t.add(grid[i--][j--]);
            }
            Collections.sort(t);
            for (int x : t) {
                grid[++i][++j] = x;
            }
        }
        return grid;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        for (int k = n - 2; k >= 0; --k) {
            int i = k, j = 0;
            vector<int> t;
            while (i < n && j < n) {
                t.push_back(grid[i++][j++]);
            }
            ranges::sort(t);
            for (int x : t) {
                grid[--i][--j] = x;
            }
        }
        for (int k = n - 2; k > 0; --k) {
            int i = k, j = n - 1;
            vector<int> t;
            while (i >= 0 && j >= 0) {
                t.push_back(grid[i--][j--]);
            }
            ranges::sort(t);
            for (int x : t) {
                grid[++i][++j] = x;
            }
        }
        return grid;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func sortMatrix(grid [][]int) [][]int {
    n := len(grid)
    for k := n - 2; k >= 0; k-- {
        i, j := k, 0
        t := []int{}
        for ; i < n && j < n; i, j = i+1, j+1 {
            t = append(t, grid[i][j])
        }
        sort.Ints(t)
        for _, x := range t {
            i, j = i-1, j-1
            grid[i][j] = x
        }
    }
    for k := n - 2; k > 0; k-- {
        i, j := k, n-1
        t := []int{}
        for ; i >= 0 && j >= 0; i, j = i-1, j-1 {
            t = append(t, grid[i][j])
        }
        sort.Ints(t)
        for _, x := range t {
            i, j = i+1, j+1
            grid[i][j] = x
        }
    }
    return grid
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function sortMatrix(grid: number[][]): number[][] {
    const n = grid.length;
    for (let k = n - 2; k >= 0; --k) {
        let [i, j] = [k, 0];
        const t: number[] = [];
        while (i < n && j < n) {
            t.push(grid[i++][j++]);
        }
        t.sort((a, b) => a - b);
        for (const x of t) {
            grid[--i][--j] = x;
        }
    }
    for (let k = n - 2; k > 0; --k) {
        let [i, j] = [k, n - 1];
        const t: number[] = [];
        while (i >= 0 && j >= 0) {
            t.push(grid[i--][j--]);
        }
        t.sort((a, b) => a - b);
        for (const x of t) {
            grid[++i][++j] = x;
        }
    }
    return grid;
}

评论