LC 对角线遍历

LC 对角线遍历

题目描述：

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

题目实例：

示例一：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

示例二：
输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
-105 <= mat[i][j] <= 105

审题：

本题对空间复杂度无要求，我们可以申请额外的空间来解题。

标准思路：

仔细观察我们发现偶数对角线向上遍历，奇数列向下遍历，所以我们的代码就可以按照这个思路遍历。

（1）先得出遍历的次数，也就是对角线的条数为i=n+m-1，所以数组遍历条件也就是i<n+m-1。
（2）在看图，对角线上的每个元素坐标之和为i,也就是元素的坐标xy与i的关系为：x+y=i
（3）如何遍历？看图中，偶数对应的对角线上的元素是从下往上遍历，而奇数对应的对角线上的元素是从上往下遍历，那么只要确定遍历的起始点和结束点就好啦！我们先看偶数对角线的起点和终点，因为奇数对角线和它相反，知道了偶数的，也不难得出奇数的的。

当i<n-1时，起始点坐标x=i，如1的x坐标为0，i也为0,结束点的横坐标x=0
当i>=n-1时，起始点坐标x=n-1,如2的x坐标为2，i也为2,结束点的纵坐标y=m-1,根据（2）中的关系式,所以得出横坐标x=i-(m-1)
所以偶数对角线遍历时起始点的x的坐标为min(i,n-1)，结束点的x坐标为max(0,i-(m-1)),而坐标y就是i-x

代码如下：

#include <vector>

using namespace std;

vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
    // 初始化结果数组
    vector<int> result;
    // 获取矩阵的行数和列数
    int m = mat.size();
    if (m == 0) return result;  // 如果矩阵为空，则直接返回空数组
    int n = mat[0].size();

    // 对角线遍历
    for (int i = 0; i < m + n - 1; ++i) {
        if (i % 2 == 0) {  // 从左上到右下
            // 根据当前对角线的位置，确定遍历的起始点和结束点
            int startX = max(0, i - m + 1);
            int endX = min(i, n - 1);
            // 遍历当前对角线上的元素
            for (int x = startX; x <= endX; ++x) {
                result.push_back(mat[i - x][x]);
            }
        } else {  // 从右下到左上
            // 根据当前对角线的位置，确定遍历的起始点和结束点
            int startX = max(0, i - n + 1);
            int endX = min(i, m - 1);
            // 遍历当前对角线上的元素
            for (int x = startX; x <= endX; ++x) {
                result.push_back(mat[x][i - x]);
            }
        }
    }

    // 返回结果数组
    return result;
}

我的解题思路：

我一开始没有看出奇偶数对角线的特点，注意力全放在了如何遍历的方向上了，我发现遍历时只需要对矩阵边界上的数据做处理，矩阵内的数据只要按照上次遍历的方向走就行了，于是我定义了四个bool类型的变量flag来记录上一次遍历的方向，如果是边界上的数据就进行转弯，如果是矩阵内的数据就按照上一次的遍历方向进行就可以了；当然还需要对一些特殊矩阵做出特殊的处理。代码如下：

#include <iostream>
#include <vector>

using namespace std;

vector<int> findDiagonalOrder(vector<vector<int>> &mat)
{
    int row = mat.size();
    int columns = mat[0].size();
    int i = 0, j = 1, r = 1;
    vector<int> answer;
    bool lowerLeft = false, right = false, upperRight = false, down = false;

    answer.resize(row * columns);

    answer[0] = mat[0][0];
    right = true;

    if (row == 1 && columns == 1)
    {
        return answer;
    }
    else if (row == 1 && columns != 1)
    {
        for (; r < columns; ++r)
        {
            answer[r] = mat[0][r];
        }
        return answer;
    }
    else if (row != 1 && columns == 1)
    {
        for (; r < row; ++r)
        {
            answer[r] = mat[r][0];
        }
        return answer;
    }

    while (i < row && j < columns)
    {
        if (i == 0 && j == columns - 1 && upperRight)
        {
            answer[r++] = mat[i][j];
            ++i;
            down = true, upperRight = false;
        }
        else if (i == 0 && j == columns - 1 && right)
        {
            answer[r++] = mat[i][j];
            ++i, --j;
            lowerLeft = true, right = false;
        }
        else if (i == 0 && right)
        {
            answer[r++] = mat[i][j];
            ++i, --j;
            right = false, lowerLeft = true;
        }
        else if (i == 0 && upperRight)
        {
            answer[r++] = mat[i][j];
            ++j;
            upperRight = false, right = true;
        }
        else if (i == row - 1 && lowerLeft)
        {
            answer[r++] = mat[i][j];
            ++j;
            lowerLeft = false, right = true;
        }
        else if (i == row - 1 && right)
        {
            answer[r++] = mat[i][j];
            --i, ++j;
            right = false, upperRight = true;
        }
        else if (j == 0 && lowerLeft)
        {
            answer[r++] = mat[i][j];
            ++i;
            lowerLeft = false, down = true;
        }
        else if (j == 0 && down)
        {
            answer[r++] = mat[i][j];
            --i, ++j;
            down = false, upperRight = true;
        }
        else if (j == columns - 1 && right)
        {
            answer[r++] = mat[i][j];
            ++i, --j;
            right = false, lowerLeft = true;
        }
        else if (j == columns - 1 && upperRight)
        {
            answer[r++] = mat[i][j];
            ++i;
            upperRight = false, down = true;
        }
        else if (j == columns - 1 && down)
        {
            answer[r++] = mat[i][j];
            ++i, --j;
            down = false, lowerLeft = true;
        }
        else if (lowerLeft)
        {
            answer[r++] = mat[i][j];
            ++i, --j;
        }
        else
        {
            answer[r++] = mat[i][j];
            --i, ++j;
        }
    }

    return answer;
}

int main(int argc, char *argv[])
{
    vector<vector<int>> myVector = {{1, 2, 3, 4, 5}};

    /*
    {{1, 2, 3, 4},
                                        {5, 6, 7, 8},
                                        {9, 10, 11, 12},
                                        {13, 14, 15, 16}}

                                        {{1, 2, 3},
                                    {4, 5, 6},
                                    {7, 8, 9}}
    */
    vector<int> answer;

    for (int i = 0; i < myVector.size(); ++i)
    {
        for (int j = 0; j < myVector[0].size(); ++j)
        {
            cout << myVector[i][j] << " ";
        }
        cout << endl;
    }

    answer = findDiagonalOrder(myVector);

    cout << endl;

    for (int i = 0; i < answer.size(); ++i)
    {
        cout << answer[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果