मान लीजिए कि हमारे पास n x m मैट्रिक्स मैट है, हमें इस मैट को तिरछे बढ़ते क्रम में ऊपर-बाएँ से नीचे दाईं ओर क्रमबद्ध करना है, ताकि विकर्णों में सभी तत्वों को क्रमबद्ध किया जा सके। तो अगर इनपुट मैट्रिक्स की तरह है -
| 3 | 3 | 1 | 1 |
| 2 | 2 | 1 | 2 |
| 1 | 1 | 1 | <टीडी>2
आउटपुट मैट्रिक्स होगा -
| 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 |
| 1 | 2 | 3 | 3 |
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
हल () नामक विधि को परिभाषित करें, इसमें si, sj और मैट्रिक्स मैट लगेगी
-
n :=पंक्तियों की संख्या और m :=स्तंभों की संख्या
-
अस्थायी नामक एक सरणी बनाएं
-
i:=si और j :=sj, और अनुक्रमणिका :=0
-
जबकि मैं
-
m[i, j] को टेम्परेचर में डालें, फिर i और j को 1 से बढ़ाएँ
-
-
अस्थायी सरणी क्रमबद्ध करें
-
सूचकांक सेट करें:=0, मैं:=सी और जे:=एसजे
-
जबकि मैं
-
चटाई [i, j]:=अस्थायी [सूचकांक]
-
i, j और अनुक्रमणिका को 1 से बढ़ाएँ
-
-
मुख्य विधि से, निम्न कार्य करें -
-
n :=पंक्तियों की संख्या और m :=स्तंभों की संख्या
-
मैं के लिए 0 से n - 1 की सीमा में, करो
-
हल करें (i, 0, मैट)
-
-
j के लिए 1 से m-1 की सीमा में, करें
-
हल (0, जे, मैट)
-
-
वापसी चटाई
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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));
} इनपुट
{{3,3,1,1},{2,2,1,2},{1,1,1,2}} आउटपुट
[[1, 1, 1, 1, ], [1, 2, 2, 2, ], [1, 2, 3, 3, ],]
