描述:
image.png解题思路:直接取对角线元素排序完在放回相应的位置即可
代码:
class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
map<int, vector<int>>mapj;
map<int, vector<int>>mapi;
for(int j = 0; j < mat[0].size(); j++) {
vector<int> tmp;
int i = 0, k = j;
while(i < mat.size() && k < mat[0].size()) {
tmp.push_back(mat[i][k]);
i++;
k++;
}
mapj[j] = tmp;
}
for(int i = 0; i < mat.size(); i++) {
vector<int> tmp;
int j = 0, k = i;
while(k < mat.size() && j < mat[0].size()) {
tmp.push_back(mat[k][j]);
j++;
k++;
}
mapi[i] = tmp;
}
map<int, vector<int>>::iterator iterj = mapj.begin();
while(iterj != mapj.end()) {
sort(iterj->second.begin(), iterj->second.end());
int l = 0, r = iterj -> first;
for (int i = 0; i < iterj->second.size(); i++) {
mat[l++][r++] = iterj->second[i];
}
iterj++;
}
map<int, vector<int>>::iterator iteri = mapi.begin();
while(iteri != mapi.end()) {
sort(iteri->second.begin(), iteri->second.end());
int r = 0, l = iteri -> first;
for (int i = 0; i < iteri->second.size(); i++) {
mat[l++][r++] = iteri->second[i];
}
iteri++;
}
return mat;
}
};
网友评论