1329.Sort the Matrix Diagonally

1329.Sort the Matrix Diagonally

难度:Medium

给你一个 m * n 的整数矩阵 mat ,请你将同一条对角线上的元素(从左上到右下)按升序排序后,返回排好序的矩阵。

Example:

输入: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]]

提示:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

思路: 分两种情况,一种是宽大于高,一种是宽小于高。 排序分三步,第一部分是左下部分的对角线排序,第二部分是右上部分的对角线排序,第三部分是中间部分对角线排序。

class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int m=mat.size();
int n=mat[0].size();
if(m>n)
{
for(int k=m-2;k>m-n;k--)
{
for(int i=k;i<m-1;i++)
for(int j=i+1;j<m;j++)
{
if(mat[i][i-k]>mat[j][j-k])
swap(mat[i][i-k], mat[j][j-k]);
}
}
for(int k=n-2;k>0;k--)
{
for(int i=k;i<n-1;i++)
for(int j=i+1;j<n;j++)
{
if(mat[i-k][i]>mat[j-k][j])
swap(mat[i-k][i], mat[j-k][j]);
}
}
for(int k=0;k<=m-n;k++)
{
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(mat[i+k][i]>mat[j+k][j])
swap(mat[i+k][i], mat[j+k][j]);
}
}
else
{
for(int k=m-2;k>0;k--)
{
for(int i=k;i<m-1;i++)
for(int j=i+1;j<m;j++)
{
if(mat[i][i-k]>mat[j][j-k])
swap(mat[i][i-k], mat[j][j-k]);
}
}
for(int k=n-m+1;k<n-1;k++)
{
for(int i=k;i<n-1;i++)
for(int j=i+1;j<n;j++)
{
if(mat[i-k][i]>mat[j-k][j])
swap(mat[i-k][i], mat[j-k][j]);
}
}
for(int k=0;k<=n-m;k++)
{
for(int i=0;i<m-1;i++)
for(int j=i+1;j<m;j++)
if(mat[i][i+k]>mat[j][j+k])
swap(mat[i][i+k], mat[j][j+k]);
}
}
return mat;
}
};

执行用时 :24 ms, 在所有 C++ 提交中击败了21.23%的用户 内存消耗 :8.4 MB, 在所有 C++ 提交中击败了100.00%的用户