LeetCode:对角线遍历【498】
题目描述
给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。
示例:
输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,4,7,5,3,6,8,9] 解释:
题目分析
首先是两种变换,一种是X++,Y--,即向左下方移动。另一种是X--,Y++,即向右上方移动。
还有要考虑6中情况,
右上方移动,会有三种出界情况,以及对应调整策略。左下方移动,同样会有三种出界情况,以及对应调整策略。需要说明的是题目给的是正方形矩阵,此处容易想当然忽略对角的情况。
具体的出界判断以及调整详见代码。PS:这道题真TMD的坑,平心静气的慢慢做!!!
Java题解
package arr; import java.util.Scanner; public class FindDiagonalOrder_498 { public static int[] findDiagonalOrder(int[][] matrix) { int flag =1; int x =0; int y=0; int m = matrix.length; if(m==0) return new int[]{}; int n = matrix[0].length; int[] res = new int[m*n]; for(int i=0;i<m*n;i++) { res[i] = matrix[x][y]; if(flag==1) { //右上角【纵坐标超了,横坐标小于0】 if(x-1<0&&y+1>n-1) { x++; flag=0; continue; } //上面【纵坐标没超,但是横坐标小于0】 if((x-1<0&&y+1<=n-1)) { y++; flag =0; continue; } //右面【横坐标大于0,纵坐标超了】 if(x-1>=0&&y+1>n-1) { x++; flag = 0; continue; } x--;y++; } else{ //左下角【横坐标超过,纵坐标小于0】 if(x+1>m-1&&y-1<0) { y++; flag=1; continue; } //下面【横坐标超了,但是纵坐标没超】 if(x+1>m-1&&y-1>=0) { y++; flag =1; continue; } //左面【横坐标没超,但是纵坐标小于0】 if(x+1<=m-1&&y-1<0) { x++; flag =1; continue; } x++;y--; } } return res; } public static void main(String[] args) { int[][] matrix = new int[][]{{1,2,3},{4,5,6}}; findDiagonalOrder(matrix); } }