LC 对角线遍历

发布时间:2024年01月21日

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;
}
运行结果

在这里插入图片描述

文章来源:https://blog.csdn.net/Kruskual/article/details/135730246
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。