मान लीजिए कि हमारे पास एन एक्स एम मैट्रिक्स है, हमें इसे तिरछे क्रम में ऊपर-बाएं से नीचे दाईं ओर बढ़ते क्रम में क्रमबद्ध करना होगा। तो अगर मैट्रिक्स की तरह है -
| 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, जे, मैट)
-
-
वापसी चटाई
उदाहरण (C++)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#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]]
