Leetcode题解
Search…
1329.Sort the Matrix Diagonally
1329.Sort the Matrix Diagonally
难度:Medium
给你一个 m * n 的整数矩阵 mat ，请你将同一条对角线上的元素（从左上到右下）按升序排序后，返回排好序的矩阵。
Example:
1
输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
2
输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
Copied!
提示：
1
m == mat.length
2
n == mat[i].length
3
1 <= m, n <= 100
4
1 <= mat[i][j] <= 100
Copied!
思路： 分两种情况，一种是宽大于高，一种是宽小于高。 排序分三步，第一部分是左下部分的对角线排序，第二部分是右上部分的对角线排序，第三部分是中间部分对角线排序。
1
class Solution {
2
public:
3
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
4
int m=mat.size();
5
int n=mat[0].size();
6
7
8
if(m>n)
9
{
10
for(int k=m-2;k>m-n;k--)
11
{
12
for(int i=k;i<m-1;i++)
13
for(int j=i+1;j<m;j++)
14
{
15
if(mat[i][i-k]>mat[j][j-k])
16
swap(mat[i][i-k], mat[j][j-k]);
17
}
18
}
19
for(int k=n-2;k>0;k--)
20
{
21
for(int i=k;i<n-1;i++)
22
for(int j=i+1;j<n;j++)
23
{
24
if(mat[i-k][i]>mat[j-k][j])
25
swap(mat[i-k][i], mat[j-k][j]);
26
}
27
28
}
29
30
for(int k=0;k<=m-n;k++)
31
{
32
for(int i=0;i<n-1;i++)
33
for(int j=i+1;j<n;j++)
34
if(mat[i+k][i]>mat[j+k][j])
35
swap(mat[i+k][i], mat[j+k][j]);
36
}
37
}
38
else
39
{
40
for(int k=m-2;k>0;k--)
41
{
42
for(int i=k;i<m-1;i++)
43
for(int j=i+1;j<m;j++)
44
{
45
if(mat[i][i-k]>mat[j][j-k])
46
swap(mat[i][i-k], mat[j][j-k]);
47
}
48
}
49
for(int k=n-m+1;k<n-1;k++)
50
{
51
for(int i=k;i<n-1;i++)
52
for(int j=i+1;j<n;j++)
53
{
54
if(mat[i-k][i]>mat[j-k][j])
55
swap(mat[i-k][i], mat[j-k][j]);
56
}
57
58
}
59
for(int k=0;k<=n-m;k++)
60
{
61
for(int i=0;i<m-1;i++)
62
for(int j=i+1;j<m;j++)
63
if(mat[i][i+k]>mat[j][j+k])
64
swap(mat[i][i+k], mat[j][j+k]);
65
}
66
}
67
return mat;
68
69
}
70
};
Copied!
执行用时 :24 ms, 在所有 C++ 提交中击败了21.23%的用户 内存消耗 :8.4 MB, 在所有 C++ 提交中击败了100.00%的用户
Copy link