Leetcode 498. 对角线遍历(C++, python) （小白学习之路）

水深无声 2023-07-12 05:24 5阅读 0赞

最近在做数组相关的题，终于碰到了一个medium难度的题目，描述如下：

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0_size_16_color_FFFFFF_t_70][]

**说明:**

1.  给定矩阵中的元素总数不会超过 100000 。

看到题目我第一个想的总是暴力法，这道题的暴力算法也不难看出，a.每条对角线的行列下标之和为定数，b.按对角线下标之和为奇数还是偶数决定是顺序还是逆序输出，所以我的第一想法就是创建一个二维数组，里面储存下标之和从0到M+N-2的新数组，然后根据下标奇偶性输出，

一开始的时候打算用C++写，然后发现C++声明二维数组至少要声明列数，这里没找到方法（虽然后来找到了），于是用python的list来解决这个问题，不得不说，在实现自然语言的思路时，python的限制真的很少，代码如下：

class Solution(object):
        def findDiagonalOrder(self, matrix):
            M = len(matrix)   # 矩阵的行数
            if M == 0:
                return []    #若行数为零，直接返回空列表；
            N = len(matrix[0])   #矩阵列数，有的题解里加了一句判断列数为0直接返回空，其实不加那一句对        # 最后的结果基本没有影响，但是行数如果不判断的话在这里就会超出下标而报错
            result = []      
            temp = []       # 储存每个对角线列表的列表
            for i in range(M + N - 1):    # 按对角线个数创建M+N-1个空列表
                temp.append([])
            for i in range(M):              
                for j in range(N):                  
                    temp[i + j].append(matrix[i][j])   # 遍历矩阵
            for i in range(len(temp)): 
                if i % 2 == 0:                          # 下标和为偶数逆序输出
                    for item in reversed(temp[i]):
                        result.append(item)
                else:
                    for item in temp[i]:               # 下标和为奇数顺序输出
                        result.append(item)
    
            return result

Python结果如下：

![20200307140348227.png][]

用时超过了83.5%的python用户，这里时间复杂度是O（M\*N），即是遍历矩阵和输出矩阵的时间，空间复杂度上，创立对角线个数组（M+N）,每个数组的最大元素个数（M+N），因此空间复杂度能达到O（（M+N）（M+N））；空间复杂度上可以有优化空间，按照官方题解的思路是设置一个中间List，每次储存结束就直接append到result数组里，这样空间复杂度可以降到O（MIN(M,N)），二刷的时候打算尝试一下；

另一种思路是按照输出轨迹来，下标和为偶数时，行数-1列数+1， 下标和为奇数时，行数+1列数-1，同时注意一下行下标和列下标超出范围时的判断方法，C++代码如下：

class Solution {
    public:
        vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
            int M = matrix.size();
            if(M==0) return {};                //行数为0直接返回空数组
            int N = matrix[0].size();
            int i = 0; int j = 0; int diag=0;
            vector<int>result;
            if (M == 0 || N == 0) return {};
            result.push_back(matrix[i][j]);
            while (i+j< M + N - 2)
            {
                diag = i + j;                 //记录行数+列数之和
                if ((i + j) % 2 == 0)
                {
                    i--; j++;                //diag为偶数，行数-1列数+1方向运动
                    if (i>=0&&i<M &&  j>=0&&j < N) result.push_back(matrix[i][j]); //下标正常，直接加入结result数组
                    else
                    {
                        diag++;             //下标不正常，行列之和必+1
                        if (i < 0 && j >= 0 && j < N) { i = 0; j = diag - i; result.push_back(matrix[i][j]); continue; }     //仅行下标越界，改行下标为0
                        if (i >= 0 && i<M && j>N - 1) { j = N - 1; i = diag - j; result.push_back(matrix[i][j]); continue; }    //仅列下标越界，改列下标为最大值
                        if (i<0 && j>N - 1) { j = N - 1; i = diag - j; result.push_back(matrix[i][j]); continue; }    //行列下标同时越界（方阵情况），先改列下标再改行下标
                    }
                }
                else
                {
                    i++; j--;               //diag为奇数，行数+1列数-1
                    if (i>=0&&i<M && j>=0&& j< N) result.push_back(matrix[i][j]); //下标正常，直接加入result数组
                    else
                    {
                        diag++;             //下标不正常，diag++
                        if (i > M - 1 && j >= 0 && j < N) { i = M - 1; j = diag - i; result.push_back(matrix[i][j]); continue; }    //仅行下标越界，改行下标为最大值
                        if (j < 0 && i >= 0 && i < M) { j = 0; i = diag - j; result.push_back(matrix[i][j]); continue; }    //仅列下标越界，改列下标为0
                        if (j<0 && i>M - 1) { i = M - 1; j = diag - i; result.push_back(matrix[i][j]); continue; }    //行列下标同时越界（方阵情况），先改行下标再改列下标，与diag为偶数情况正好相反
    
                    }
                }
            }
            return result;
    
        }
    };

结果如下：

![20200307142055247.png][]

用时战胜了90.89%的C++用户，回头看，此解法的时间复杂度为O（M\*N），仅需遍历一次矩阵，空间复杂度为常数级，效率上C++远强于Python，但是这种思路的有个弊端就是太多If判断，做题时想过合并两个if，发现两者还不能合并，只能把代码写的如此冗长、后来看到了一些C++大神的思路，确实豁然开朗，比如行列之和为偶数时直接判断起始数的列数为0或者diag-M+1,可以减去一些if判断句，这里先Mark住，二刷时更新做法，见证自己的进步。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200307135128716.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0,size_16,color_FFFFFF,t_70
[20200307140348227.png]: https://img-blog.csdnimg.cn/20200307140348227.png
[20200307142055247.png]: https://img-blog.csdnimg.cn/20200307142055247.png