LeetCode 1329中等数组 · 哈希
将矩阵按对角线排序 图解题解
这道题到底在问什么
先把对角线认清楚。所谓矩阵对角线,是沿着右下方向走的那种斜线,比如从 (0,0) 出发会经过 (0,0)、(1,1)、(2,2),从 (1,0) 出发会经过 (1,0)、(2,1)。关键规律是:同一条对角线上的格子,行号减列号 i-j 的值都相等。比如主对角线上 (0,0)、(1,1)、(2,2) 的 i-j 都是 0。题目要的是把每一条这样的对角线单独拎出来,线上的数按升序重新摆好,其余位置不动。注意是沿右下的对角线,不是沿右上的反对角线 i+j。
- 输入
- 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]]
- 输入
- 主对角线 (0,0)(1,1)(2,2) 上的数 3、2、1
- 输出
- 升序排成 1、2、3,再写回这三格
- 输入
- 怎么判断两格在同一条对角线
- 输出
- 看 i-j 是否相等,相等就在同一条
最优解：一步一步想明白
- 3三步走:按 i-j 把格子分到各条对角线,每条单独升序,再沿右下从上往下把数从小到大写回。i-j 可能为负,记得偏移成非负下标。
- 4这是要处理的 3 行 4 列矩阵,行号 i 从上到下 0、1、2,列号 j 从左到右 0 到 3。接下来一条一条对角线来处理:每条线先整体点亮、收集线上的数,再升序排好,然后从最上面那格起把数从小到大写回。处理完的格子会标成蓝色定稿,正在处理的标橙色。先看主对角线。
- 5点亮的是 i-j 等于 0 这条对角线,经过 (0,0)、(1,1)、(2,2)。沿右下从上往下把数收集起来,得到 3、2、1。右边面板就是这条线现在的原始排列,还没排序。
- 6把刚收集的 3、2、1 单独升序排一下,得到 1、2、3。注意只在这条对角线内部排,不和别的对角线混。排好后就该把它们从上往下写回去,最小的写在最靠左上的那格。
- 7把这条线第 1 小的数 1 写进格子 (0,0)。它是从上往下第 1 个位置,正好放第 1 小的数。右边面板里还剩 2、3,等着填进更靠右下的格子。
- 8把这条线第 2 小的数 2 写进格子 (1,1)。它是从上往下第 2 个位置,正好放第 2 小的数。右边面板里还剩 3,等着填进更靠右下的格子。
- 9把这条线最大的数 3 写进格子 (2,2)。它是从上往下第 3 个位置,正好放第 3 小的数。这条对角线已经全部就位。
- 10点亮的是 i-j 等于 -1 这条对角线,经过 (0,1)、(1,2)、(2,3)。沿右下从上往下把数收集起来,得到 3、1、2。右边面板就是这条线现在的原始排列,还没排序。
- 11把刚收集的 3、1、2 单独升序排一下,得到 1、2、3。注意只在这条对角线内部排,不和别的对角线混。排好后就该把它们从上往下写回去,最小的写在最靠左上的那格。
- 12把这条线第 1 小的数 1 写进格子 (0,1)。它是从上往下第 1 个位置,正好放第 1 小的数。右边面板里还剩 2、3,等着填进更靠右下的格子。
- 13把这条线第 2 小的数 2 写进格子 (1,2)。它是从上往下第 2 个位置,正好放第 2 小的数。右边面板里还剩 3,等着填进更靠右下的格子。
- 14把这条线最大的数 3 写进格子 (2,3)。它是从上往下第 3 个位置,正好放第 3 小的数。这条对角线已经全部就位。
- 15点亮的是 i-j 等于 -2 这条对角线,经过 (0,2)、(1,3)。沿右下从上往下把数收集起来,得到 1、2。右边面板就是这条线现在的原始排列,还没排序。
- 16把刚收集的 1、2 单独升序排一下,得到 1、2。注意只在这条对角线内部排,不和别的对角线混。排好后就该把它们从上往下写回去,最小的写在最靠左上的那格。
- 17把这条线第 1 小的数 1 写进格子 (0,2)。它是从上往下第 1 个位置,正好放第 1 小的数。右边面板里还剩 2,等着填进更靠右下的格子。
- 18把这条线最大的数 2 写进格子 (1,3)。它是从上往下第 2 个位置,正好放第 2 小的数。这条对角线已经全部就位。
- 19这条对角线只有一个格子 (0,3),值是 1。单个元素本身就是升序,不用排也不用动,直接定稿。
- 20点亮的是 i-j 等于 1 这条对角线,经过 (1,0)、(2,1)。沿右下从上往下把数收集起来,得到 2、1。右边面板就是这条线现在的原始排列,还没排序。
- 21把刚收集的 2、1 单独升序排一下,得到 1、2。注意只在这条对角线内部排,不和别的对角线混。排好后就该把它们从上往下写回去,最小的写在最靠左上的那格。
- 22把这条线第 1 小的数 1 写进格子 (1,0)。它是从上往下第 1 个位置,正好放第 1 小的数。右边面板里还剩 2,等着填进更靠右下的格子。
- 23把这条线最大的数 2 写进格子 (2,1)。它是从上往下第 2 个位置,正好放第 2 小的数。这条对角线已经全部就位。
- 24这条对角线只有一个格子 (2,0),值是 1。单个元素本身就是升序,不用排也不用动,直接定稿。
- 25六条对角线全部处理完。现在每一条从左上到右下的对角线都是升序的:主对角线是 1、2、3,它上面那条是 1、2、3,顶上和最左边那些短对角线也都各自升序。拼起来就是答案,第一行 1、1、1、1,第二行 1、2、2、2,第三行 1、2、3、3。整个过程就是分组、排序、写回这三步反复做。
⚠️ 容易写错的地方
✗ 错：把对角线判成 i+j 相等
✓ 对：右下方向的对角线是 i-j 相等;i+j 相等是右上的反对角线,方向相反
题目明确是从上或从左出发、朝右下走的对角线,只有 i-j 在这条线上保持不变;用 i+j 会排错成另一组斜线
✗ 错：i-j 当数组下标直接用,负数越界
✓ 对：用 m-i+j 或 i-j+n 之类的偏移挪成非负,或干脆用哈希表按 i-j 归桶
i 小 j 大时 i-j 是负的,负下标在数组里越界;偏移一个常数把所有对角线编号压进 0 到 m+n-1 这个区间就安全了
✗ 错：排好后写回的方向或顺序搞反
✓ 对：沿右下从最上面那格往下走,把升序结果从小到大依次填,最小放左上、最大放右下
题目要的是每条对角线升序,左上是这条线的起点、应放最小值;若从右下往左上写、或降序写回,结果就反了
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
m, n = len(mat), len(mat[0])
g = [[] for _ in range(m + n)]
for i, row in enumerate(mat):
for j, x in enumerate(row):
g[m - i + j].append(x)
for e in g:
e.sort(reverse=True)
for i in range(m):
for j in range(n):
mat[i][j] = g[m - i + j].pop()
return matC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<int> g[m + n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
g[m - i + j].push_back(mat[i][j]);
}
}
for (auto& e : g) {
sort(e.rbegin(), e.rend());
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
mat[i][j] = g[m - i + j].back();
g[m - i + j].pop_back();
}
}
return mat;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int[][] diagonalSort(int[][] mat) {
int m = mat.length, n = mat[0].length;
List<Integer>[] g = new List[m + n];
Arrays.setAll(g, k -> new ArrayList<>());
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
g[m - i + j].add(mat[i][j]);
}
}
for (List<Integer> e : g) {
Collections.sort(e, (a, b) -> b - a);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
mat[i][j] = g[m - i + j].remove(g[m - i + j].size() - 1);
}
}
return mat;
}
}复杂度
时间
O(m·n·log(min(m,n)))
每个格子被收集和写回各一次,是 O(m·n);真正的开销在排序,每条对角线最长 min(m,n) 个数,所有对角线加起来共 m·n 个数、按对角线分段排序,总排序量是 O(m·n·log(min(m,n)))
空间
O(m·n)
按峰值算:参考代码把全部 m·n 个数都分散存进了各个桶,额外占 O(m·n)。若改成一条对角线处理完再处理下一条,辅助空间可压到一条线的长度 O(min(m,n))。排序自身的栈开销被桶占用量覆盖
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 将矩阵按对角线排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么同一条右下对角线上的 i-j 是个常数?+
从对角线起点出发,每走一步都是往右下,行号加 1、列号也加 1,差 i-j 一减一加正好抵消,保持不变。所以一条对角线可以用它共同的 i-j 值来唯一标识,分组时按这个值归桶即可。反对角线是往右上走、行减列加,变的是 i-j、不变的是 i+j。
参考代码明明排的是降序,怎么最后矩阵是升序的?+
它把每个桶按降序排,降序数组的末尾就是最小值。写回时按行列顺序遍历矩阵,同一条对角线总是先遇到最靠左上的格子,而每次都从桶尾弹出当前最小的数填进去,于是最小的落在左上、次小的落在它右下,一路下来就是升序。这是用一次降序排序加从尾弹出,等价地得到升序写回,省了反转。
这题和直接对整个矩阵排序有什么本质区别?复杂度怎么算?+
本质区别是排序的粒度:不是整体排,而是把矩阵切成 m+n-1 条互不相干的对角线,各自独立排序。每条最长 min(m,n) 个数,所有数加起来是 m·n 个,分段排序总量是 O(m·n·log(min(m,n)))。空间上参考代码用桶存了全部元素,是 O(m·n);如果一条线处理完再处理下一条,可以降到一条线的长度 O(min(m,n))。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 将矩阵按对角线排序 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。