Sắp xếp ma trận theo đường chéo trong C ++

Giả sử chúng ta có N x M ma trận, chúng ta phải sắp xếp ma trận này theo đường chéo theo thứ tự tăng dần từ trên cùng bên trái đến dưới cùng bên phải. Vì vậy, nếu ma trận giống như -

Ma trận đầu ra sẽ là -

Để 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

• cho tôi trong phạm vi từ 0 đến n - 1

  • giải quyết (i, 0, mat)

• cho j trong phạm vi từ 1 đến m - 1

  • giải quyết (0, j, mat)

• chiếu trở lại

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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]]