LeetCode 题解工作台
按对角线进行矩阵排序
给你一个大小为 n x n 的整数方阵 grid 。返回一个经过如下调整的矩阵： 左下角三角形 （包括中间对角线）的对角线按 非递增顺序 排序。 右上角三角形 的对角线按 非递减顺序 排序。 示例 1： 输入： grid = [[1,7,3],[9,8,2],[4,5,6]] 输出： [[8,2,3…
3
题型
8
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
我们可以按照题目描述的要求，模拟对角线的排序过程。 我们首先对左下角三角形的对角线进行排序，然后对右上角三角形的对角线进行排序。最后返回排序后的矩阵即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你一个大小为 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 == n1 <= n <= 10-105 <= grid[i][j] <= 105
解题思路
方法一：模拟 + 排序
我们可以按照题目描述的要求，模拟对角线的排序过程。
我们首先对左下角三角形的对角线进行排序，然后对右上角三角形的对角线进行排序。最后返回排序后的矩阵即可。
时间复杂度 ，空间复杂度 。其中 是矩阵的大小。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They expect you to notice that row minus column uniquely identifies a top-left to bottom-right diagonal.
- question_mark
They want you to separate the main diagonal plus bottom-left triangle from the top-right triangle because the sort directions differ.
- question_mark
They are checking whether you can rebuild the matrix cleanly after sorting each diagonal instead of forcing a brittle in-place swap process.
常见陷阱
外企场景- error
Using the same ascending order for every diagonal, which breaks the main diagonal and lower-left diagonals.
- error
Keying diagonals incorrectly with row plus column, which groups anti-diagonals instead of the required diagonals.
- error
Starting diagonals from every cell and sorting duplicates multiple times, which adds bugs and unnecessary work.
进阶变体
外企场景- arrow_right_alt
Sort all diagonals in ascending order only, which removes the need to branch on diagonal position.
- arrow_right_alt
Apply the same diagonal-bucketing idea to rectangular matrices where lengths differ across diagonals.
- arrow_right_alt
Sort anti-diagonals instead of main-direction diagonals, which changes the grouping key from row minus column to row plus column.