题目描述: 矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线,沿右下方向一直到矩阵末尾的元素。例如,矩阵 mat 有 6 行 3 列,从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。
给你一个 m * n 的整数矩阵 mat ,请你将同一条 矩阵对角线 上的元素按升序排序后,返回排好序的矩阵。
思路: 题意为对每一根对角线进行排序,根据题意不难判断,每一根的对角线的起始点都是第一行或者第一列,对角线下一个点的坐标就是上一个点的横纵坐标 + 1;由此可以使用一个临时数组来存储对角线的值,然后对临时数组进行排序,再根据排好序的数组来重写填写原数组
代码如下:
class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int n = mat.size(),m = mat[0].size(); //获取行的长度跟列的长度
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
if(i == 0 || j == 0) { //如果是起始坐标
vector<int> tmp; //构建一个临时数组
for(int k = 0; k + i < n&& k + j < m; k++) { //将该对角线存入临时数组
tmp.push_back(mat[k+i][k+j]);
}
sort(tmp.begin(),tmp.end()); //对临时数组排序
for(int s = 0; s + i <n && s + j < m; s ++) { //重新插入原数组
mat[s+i][s+j] = tmp[s];
}
}
}
}
return mat;
}
};