comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3446.Sort%20Matrix%20by%20Diagonals/README.md	数组 矩阵 排序

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

English Version

题目描述

给你一个大小为 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$ 是矩阵的大小。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}