面试刷题：矩阵对角线排序
By 青衣极客 Blue Geek In 2020-04-10
排序作为一种基本算法，已经不太可能直接作为面试题，但是 以排序作为基础内核来解决问题仍然是一个不错的出题点。Leetcode Q1329 就是一个很好的例子，难度并不大，却可以很好地检查开发者运用基础的排序算法解决问题的能力。这远比手动写一个大顶堆或者红黑树有意义得多，毕竟真实工作中大家不太可能这样做。
1. 题目 Q1329 矩阵对角线排序
给定一个 $m \times n$ 整数矩阵，按从左上角到右下角的 升序对角 对其进行排序，然后返回排序后的数组。
约束条件：
(a) m == mat.length
(b) n == mat[i].length
(c) 1 <= m, n <= 100
(d) 1 <= mat[i][j] <= 100
示例1
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
解释：
2. 解题思路
题意已经描述地很清楚了，就是每个对角线单独进行升序的排序。不过我们需要知道一点，即矩阵并不一定就是方阵。我们可以 逐个取出对角线元素，然后针对这些元素使用快速排序算法按升序排列，最后再将排序完成的元素回填到矩阵之中的对应位置处。
按照这个思路，排序已经不是难点了，真正的难点变成了按照对角线取元素和回填元素。从实现的角度来看，对左上角的对角线和右下角的对角线提取元素的方式还稍有差别，因此需要分开处理。
3. C++解决方案
按照以上的思路，这里给出C++的解决方案。
class Solution {
public:
// Runtime: 28 ms, faster than 88.50%
// Memory Usage: 10.6 MB, less than 100.00%
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int m = mat.size();
int n = mat[0].size();
vector<int> buff; // avoid creating object repeatedly
int r = 0, c = 0;
// sort right-up
for (int i=0; i<n; ++i) {
buff.clear();
r = 0, c = i;
while(r < m && c < n) {
buff.push_back(mat[r++][c++]);
}
// sort diag
sort(buff.begin(), buff.end());
// fill into mat
r = 0, c = i;
for (auto & v : buff) {
mat[r++][c++] = v;
}
}
// sort left-bottom
for (int i=1; i<m; ++i) {
buff.clear();
r = i, c = 0;
while (r < m && c < n) {
buff.push_back(mat[r++][c++]);
}
// sort diag
sort(buff.begin(), buff.end());
// fill into mat
r = i, c = 0;
for (auto & v : buff) {
mat[r++][c++] = v;
}
}
return mat;
}
};
在实现上需要说明的是，尽量减少零时变量的创建次数，尽量预先使用reserve()函数为vector分配内存。对于“前++”和“后++”这两种语法的使用可以使代码更简洁，如果解决可读性下降，也可以拆分开编写。
题外：
本频道创建了一个代码库专门用于管理和自动化测试Leetcode刷题代码，如果需要更方便地获取源码或者贡献解决方案，可以查看仓库：leetcode
COMMENT
博客评论区功能由Github Issue提供，提交Issue时请以本文标题为话题。
"BG84-面试刷题：矩阵对角线排序 Q1329"