美文网首页爱写Bug
Leetcode 498:对角线遍历Diagonal Trave

Leetcode 498:对角线遍历Diagonal Trave

作者: 爱写Bug | 来源:发表于2019-06-05 14:25 被阅读0次

    对角线遍历

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

    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.

    示例:

    输入:
    [
     [ 1, 2, 3 ],
     [ 4, 5, 6 ],
     [ 7, 8, 9 ]
    ]
    输出:  [1,2,4,7,5,3,6,8,9]
    
    

    解释:

    diagonal_traverse.png

    说明:

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

    思路

    ​ 实例输入的二维数组范围均是0~2

    ​ 先观察一下遍历规律:(0,0)->(0,1)->(1,0)->(2,0)->(1,1)->(0,2)->(1,2)->(2,1)->(2,2)

    ​ 数组索引(m,n),两种改变方式1、(m-1,n+1) 2、(m+1,n-1)

    ​ 数组从(0,0)开始,先是(m-1,n+1) ,(0,0)->(-1,1)此时m=-1,超出范围,m赋值0。然后切换索引改变方式(m+1,n-1),执行两次(0,1)->(1,0)->(2,-1),n赋值0得到(2,0),再次切换为索引改变方式(m-1,n+1)直到下次超出范围(2,0)->(1,1)->(0,2)->(-1,3)。此时m<0且n>2均超出范围,(m+2,n-1),应当优先判断n是否超出范围,执行(m+2,n-1)->(1,2),避免因为m<0再次切换一次索引改变方式。然后正常切换后:(1,2)->(2,1)->(3,0),因为m>2,切换方式并(m-1,n+2)

    java:

    class Solution {
        public int[] findDiagonalOrder(int[][] matrix) {
            if (matrix.length==0||matrix[0].length==0)return new int[0];
            int col=matrix.length,row=matrix[0].length;
            int nums=col*row,m=0,n=0;
            int res[]=new int[nums];
            boolean flag=true;
    
            for(int i=0;i<nums;i++){
                res[i]=matrix[m][n];
                if(flag){
                    n+=1; m-=1;
                }else{
                    n-=1; m+=1;
                }
                if(m>=col){
                    m-=1; n+=2; flag=true;
                }else if(n>=row){
                    n-=1; m+=2; flag=false;
                }
                if(m<0){
                    m=0; flag=false;
                }else if(n<0){
                    n=0; flag=true;
                }
            }
            return res;
        }
    }
    

    注意点:

    if (matrix.length==0||matrix[0].length==0)return new int[0];首先判断是否为空数组,另外 matrix.length==0||matrix[0].length==0 判断条件顺序不能颠倒,因为如果 matrix.length==0 后面的 matrix[0].length==0 不会再判断,即返回空数组;但是matrix[0].length==0 在前时,如果输入数组为空,matrix[0] 会报错因为matrix并没有0号索引。

    ​ for循环里应当先判断m、n是否大于或等于各自的最大长度,然后执行(m-1,n+2)、(m+2,n-1)。避免出现m、n同时小于0时flag布尔值转换两次的错误。

    python:

    class Solution:
        def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
            if(len(matrix)==0 or len(matrix[0])==0):
                return []
            col=len(matrix)
            row=len(matrix[0])
            nums=col*row
            m=n=0
            flag=True
            res=[]
            for i in range(nums):
                res.append(matrix[m][n])
                if flag:
                    m-=1
                    n+=1
                else:
                    m+=1
                    n-=1
                if m>=col:
                    m-=1
                    n+=2
                    flag=True
                elif n>=row:
                    m+=2
                    n-=1
                    flag=False
                if m<0:
                    m=0
                    flag=False
                elif n<0:
                    n=0
                    flag=True
            return res
    

    相关文章

      网友评论

        本文标题:Leetcode 498:对角线遍历Diagonal Trave

        本文链接:https://www.haomeiwen.com/subject/yhzjxctx.html