C ++中的对角遍历
假设我们有一个由MxN个元素组成的矩阵,我们必须以对角线顺序查找矩阵中的所有元素。所以如果矩阵像-
输出将是[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, ]