C ++中的对角遍历

假设我们有一个由M x N个元素组成的矩阵，我们必须以对角线顺序查找矩阵中的所有元素。所以如果矩阵像-

输出将是[1,2,4,7,5,3,6,8,9]

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

• 设置数组ret，设置row：= 0和col：= 0，n：=行数，m：= col数，下：= false

• 对于i，范围为0至n – 1

• 将Matrix [x，y]插入到temp中，将x减少1，将y增加1

• x：= i，y：= 0

• 创建一个数组临时

• 当x> = 0且y <m时

• 如果down为true，则反转temp数组

• 对于范围从0到temp – 1的i，将temp [i]插入ret

• down：=倒数的倒数

• 对于我，范围从1到m – 1

• 将Matrix [x，y]插入到temp中，将x减少1，并将y增加1

• x：= n – 1，y：= 1，创建数组温度

• 当x> = 0且y <m时，

• 对于范围从0到temp – 1的i，将temp [i]插入ret

• down：=倒数的倒数

• 返回ret。

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

示例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
      vector <int> ret;
      int row = 0;
      int col = 0;
      int n = matrix.size();
      int m = n? matrix[0].size() : 0;
      bool down = false;
      for(int i = 0; i < n; i++){
         int x = i;
         int y = 0;
         vector <int> temp;
         while(x >= 0 && y < m){
            temp.push_back(matrix[x][y]);
            x--;
            y++;
         }
         if(down) reverse(temp.begin(), temp.end());
         for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i]);
         down = !down;
      }
      for(int i = 1; i < m; i++){
         int x = n - 1;
         int y = i;
         vector <int> temp;
         while(x >= 0 && y < m){
            temp.push_back(matrix[x][y]);
            x--;
            y++;
         }
         if(down) reverse(temp.begin(), temp.end());
         for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i]);
         down = !down;
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
   Solution ob;
   print_vector(ob.findDiagonalOrder(v));
}

输入值

[[1,2,3],[4,5,6],[7,8,9]]

输出结果

[1, 2, 4, 7, 5, 3, 6, 8, 9, ]