Giả sử chúng ta có n x m ma trận Mat, chúng ta phải sắp xếp Mat này theo đường chéo theo thứ tự tăng dần từ trên trái xuống dưới cùng bên phải, để tất cả các phần tử trong đường chéo đều được sắp xếp. Vì vậy, nếu ma trận đầu vào giống như -
| 3 | 3 | 1 | 1 |
| 2 | 2 | 1 | 2 |
| 1 | 1 | 1 | 2 |
Ma trận đầu ra sẽ là -
| 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 |
| 1 | 2 | 3 | 3 |
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một phương thức có tên là giải quyết (), phương thức này sẽ lấy si, sj và mat ma trận
-
n:=số hàng và m:=số cột
-
tạo một mảng được gọi là tạm thời
-
i:=si và j:=sj và index:=0
-
trong khi tôi
-
chèn m [i, j] vào nhiệt độ, sau đó tăng i và j lên 1
-
-
sắp xếp mảng tạm thời
-
đặt chỉ mục:=0, i:=si và j:=sj
-
trong khi tôi
-
mat [i, j]:=temp [index]
-
tăng i, j và chỉ số lên 1
-
-
từ phương thức chính, hãy làm như sau -
-
n:=số hàng và m:=số cột
-
đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện
-
giải quyết (i, 0, mat)
-
-
đối với j trong phạm vi từ 1 đến m - 1, thực hiện
-
giải quyết (0, j, mat)
-
-
chiếu trở lại
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
void solve(int si, int sj, vector < vector <int> > &mat){
int n = mat.size();
int m = mat[0].size();
vector <int> temp;
int i = si;
int j = sj;
int idx = 0;
while(i < n && j < m){
temp.push_back(mat[i][j]);
i++;
j++;
}
sort(temp.begin(), temp.end());
idx = 0;
i = si;
j = sj;
while(i < n && j < m){
mat[i][j] = temp[idx];
i++;
j++;
idx++;
}
}
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
for(int i = 0; i <n; i++){
solve(i, 0, mat);
}
for(int j = 1; j < m; j++){
solve(0, j, mat);
}
return mat;
}
};
main(){
vector<vector<int>> v = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
Solution ob;
print_vector(ob.diagonalSort(v));
} Đầu vào
{{3,3,1,1},{2,2,1,2},{1,1,1,2}} Đầu ra
[[1, 1, 1, 1, ], [1, 2, 2, 2, ], [1, 2, 3, 3, ],]