leetcode498-对角线遍历

这是一个Z字形编排问题,JEPG的编码过程中也会用到。

原题

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

示例:

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

leetcode498-对角线遍历

说明:

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

解法

思想

找拐点的规律:

  1. 当横坐标x为0,纵坐标y是偶数,且y不是最后一列的时候,拐点向右。
  2. 当横坐标x为最后一行,若行数为偶数且纵坐标y为奇数或行数为奇数但纵坐标y为偶数时,拐点向右。
  3. 当纵坐标y为0,横坐标x是奇数,且x不是最后一行的时候,拐点向下。
  4. 当纵坐标y为最后一列,若列数为偶数且横坐标x为偶数或列数为奇数但横坐标x为奇数时,拐点向右。
  5. 其他情况,当横坐标x为偶数且纵坐标y为奇数或x为奇数且y为偶数的时候,拐点向左下
  6. 当横坐标x为偶数且纵坐标y为偶数或x为奇数且y为奇数的时候,拐点向右上

代码

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        //获取二维数组的长宽、大小
        int x = matrix.length;
        if(x == 0) return new int[0];
        int y = matrix[0].length;
        int size = x*y;

        int x_now=0,y_now=0;//落点位置
        int[] ret = new int[size];//用于存储并返回的一维数组
        int i = 0;
        while( x_now < x && y_now < y ){
            ret[i] = matrix[x_now][y_now]; //存入元素
            i++;
            if((x_now==0&&y_now%2==0&&y_now!=y-1)||(x_now == x-1&&(y_now+x)%2==0)){//向右
                y_now += 1;
            }else if((y_now==0&&x_now%2==1&&x_now!=x-1)||(y_now == y-1&&(x_now+y)%2==1)){//向下
                x_now += 1;
            }
            else if((x_now+y_now)%2==0){//向右上
                y_now +=1;
                x_now -=1;
            }else if((x_now+y_now)%2==1){//向左下
                y_now -=1;
                x_now +=1;
            }
        }
        return ret;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode498-%e5%af%b9%e8%a7%92%e7%ba%bf%e9%81%8d%e5%8e%86/

发表评论

电子邮件地址不会被公开。