मान लीजिए हमारे पास 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 |
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- solve() फ़ंक्शन परिभाषित करें जो प्रारंभिक सूचकांक (si, sj) और मैट्रिक्स लेता है।
- पंक्तियों (n) और स्तंभों (m) की संख्या निर्धारित करें।
- एक अस्थायी सरणी
tempबनाएं। - i = si, j = sj और index = 0 से शुरू करें।
- जब तक i < n और j < m हो, मैट्रिक्स के तत्वों को
tempमें डालें और i, j को 1 से बढ़ाएं। tempसरणी को सॉर्ट करें।- फिर से i = si, j = sj और index = 0 सेट करें।
- जब तक i < n और j < m हो, मैट्रिक्स के तत्वों को सॉर्ट किए गए
tempसे बदलें और i, j, index बढ़ाएं। - मुख्य फ़ंक्शन में:
- सभी पंक्तियों के लिए (i = 0 से n-1 तक)
solve(i, 0, mat)कॉल करें। - सभी स्तंभों के लिए (j = 1 से m-1 तक)
solve(0, j, mat)कॉल करें। - अंत में सॉर्ट किया गया मैट्रिक्स वापस करें।
C++ कार्यान्वयन उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int>> 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, j = sj, 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;
}
};
int main() {
vector<vector<int>> v = {{3,3,1,1},{2,2,1,2},{1,1,1,2}};
Solution ob;
print_vector(ob.diagonalSort(v));
return 0;
}
इनपुट
[[3,3,1,1],[2,2,1,2],[1,1,1,2]]
आउटपुट
[[1,1,1,1],[1,2,2,2],[1,2,3,3]]