假设我们有一个由M x N个元素组成的矩阵,我们必须以对角线顺序查找矩阵中的所有元素。所以如果矩阵像-
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
输出将是[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, ]