数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的对角线遍历
假设我们有一个 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 := 列数，down := false
- 对于 i 的范围从 0 到 n – 1
- x := i，y := 0
- 创建一个数组 temp
- 当 x >= 0 且 y < m 时，执行以下操作
- 将 matrix[x,y] 插入到 temp 中，并将 x 减 1，y 加 1
- 如果 down 为 true，则反转 temp 数组
- 对于 i 的范围从 0 到 temp 的大小 – 1，将 temp[i] 插入到 ret 中
- down := down 的反值
- 对于 i 的范围从 1 到 m – 1
- x := n – 1，y := 1，创建一个数组 temp
- 当 x >= 0 且 y < m 时，
- 将 matrix[x, y] 插入到 temp 中，并将 x 减 1，y 加 1
- 对于 i 的范围从 0 到 temp 的大小 – 1，将 temp[i] 插入到 ret 中
- down := 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, ]
更新于: 2020年5月2日
1K+ 次查看
广告