C ++中的对角遍历

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

123
456
789

输出将是[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, ]