使用 C++ 对矩阵的每个对角线元素按升序排序的程序

假设我们有 n x m 矩阵 Mat，我们必须按从左上到右下的升序对这个 Mat 进行对角线排序，以便对角线上的所有元素都已排序。因此，如果输入矩阵为 −

输出矩阵将是 −

为了解决这个问题，我们将遵循以下步骤 −

• 定义一个名为solve()的方法，它将采用si、sj和矩阵mat

• n := 行数和m := 列数

• 创建一个名为temp的数组

• i:= si和j := sj，以及索引:= 0

• 当 i < n 且 j < m 时，执行

  • 将 m[i, j] 插入到 temp 中，然后将 i 和 j 增加 1

• 对 temp 数组进行排序

• 设置 index := 0，i := si 且 j := sj

• 当 i < n 且 j < m

  • mat[i, j] := temp[index]

  • 将 i、j 和 index 增加 1

• 从主方法中，执行以下操作 −

• n := 行数和 m := 列数

• 对于范围从 0 到 n – 1 的 i，执行

  • solve(i, 0, mat)

• 对于范围从 1 到 m – 1，执行

  • solve(0，j，mat)

• 返回 mat

让我们看看下面的实现以便更好地理解 −

示例

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

相关文章

• 用 Python 编写程序，求出排序列表中每对数字的绝对差之和
• 用 Python 编写程序，查找使列表元素相等的最小总成本
• 用 Python 编写的程序，通过使用左子树和右子树本身的值来更新值，从而找到一棵树
• 用 Python 中的字符串字符计算我们可以生成的唯一回文数的程序
• 用 Python 计算顶点到顶点可达性矩阵的程序
• 用 Python 编写程序来计算投掷 n 个骰子的方法数
• 用 Python 编写的程序，用于查找赢得删除重复整数游戏所需的移动次数
• 用 Python 编写一个程序，通过从第一个或最后一个字符中删除并再次插入来制作目标
• 用 Python 编写的程序，用于从二叉树中删除所有具有偶数值的叶子
• 用 Python 编写程序，找出解码消息的方法数量

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/