leetcode 498. Diagonal Traverse 矩阵对角遍历 + 控制方向即可

我会带着你远行 2022-06-03 00:55 141阅读 0赞

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:  
Input:  
\[  
\[ 1, 2, 3 \],  
\[ 4, 5, 6 \],  
\[ 7, 8, 9 \]  
\]  
Output: \[1,2,4,7,5,3,6,8,9\]  
Explanation:  
![这里写图片描述][SouthEast]  
Note:  
The total number of elements of the given matrix will not exceed 10,000.

本题题意很简单，就是对矩阵做一个对角遍历，其实可以遍历所有的对角，然后依次插入即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<int> findDiagonalOrder(vector<vector<int>>& mat)
        {
            vector<int> res;
            if (mat.size() <= 0)
                return res;
            int row = mat.size(), col = mat[0].size();
            for (int i = 0; i < row + col - 1; i++)
            {
                int x, y;
                if (i <= row - 1)
                {
                    x = i;
                    y = 0;
                }
                else
                {
                    x = row - 1;
                    y = i - row + 1;
                }
                vector<int> one;
                while (x >= 0 && y < col)
                    one.push_back(mat[x--][y++]);
    
                if (i % 2 == 0)
                {
                    for (int j = 0; j<one.size(); j++)
                        res.push_back(one[j]);
                }
                else
                {
                    for (int j = one.size() - 1; j >= 0; j--)
                        res.push_back(one[j]);
                }
            }
            return res;
        }
    };

[SouthEast]: /images/20220603/4cd84daeaf054523a9c760582de62dcd.png