给定一个矩阵,从第一个元素A[0][0]开始按左下↙️、右上↗、左下↙️、右上↗...类似蛇形状的顺序遍历,直到遍历完矩阵的所有元素,按遍历的顺序返回所有的元素 提示:矩阵不一定是方正
A:待遍历的矩阵 n:矩阵A的行数 m:矩阵A的列数
按蛇形状遍历矩阵的结果
A: 1,2,3 4,5,6 7,8,9 n:3, m:3
1,4,2,3,5,7,8,6,9
以题目给例子寻找输出的规律,可以将输出的过程分为5个矩阵的对角线元素输出的过程,具体如下:
(1)第一个对角线上的元素为1,按照左下的方向输出1
(2)第二个对角线上的元素为4,2,按照右上的方向输出4,2
(3)第三个对角线上的元素为7,5,3,按照左下的方向输出3,5,7
(4)第四个对角线上的元素为8,6,按照右上的方向输出8,6
(5)第5个对角线上的元素为9,按照左下的方向输出9
通过上述的分析,我们可以发现,只要循环获取矩阵的所有对角线上的元素即可,循环的总次数为矩阵的总对角线个数,也就是(矩阵的行数+列数-1)。需要注意的是第奇数个对角线上的元素按照左下的方向输出,第偶数个对角线上的元素按照右上的方向输出。
import java.util.*; public class Main{ //按照左下方向输出对角线上的元素 public List<Integer> leftDown(int[][] input, int n, int startX, int startY){ List<Integer> diagList = new ArrayList<>(); while(startX<=n-1 && startY>=0){ diagList.add(input[startX][startY]); startX++; startY--; } return diagList; } //按照右上方向输出对角线元素 public List<Integer> rightUp(int[][] input, int m, int startX, int startY){ List<Integer> diagList = new ArrayList<>(); while(startX>=0 && startY<=m-1){ diagList.add(input[startX][startY]); startX--; startY++; } return diagList; } public int[] solution(int[][] input, int n, int m){ if(input == null){ return null; } boolean leftDownFlag = true; List<Integer> matrixList = new ArrayList<>(); int diagLineNumber = n+m-1; int startX, startY; for(int i=0; i<diagLineNumber; i++){ if(leftDownFlag){//第奇数个对角线 if(i<m){ startX=0; startY=i; }else{ startX=i+1-m; startY=m-1; } matrixList.addAll(leftDown(input, n, startX, startY)); }else{//第偶数个对角线 if(i<n){ startX=i; startY=0; }else{ startX=n-1; startY=i+1-n; } matrixList.addAll(rightUp(input, m, startX, startY)); } leftDownFlag=!leftDownFlag;//更新标记变量 } int length = matrixList.size(); int[] output = new int[length]; for(int i=0; i<length; i++){ output[i] = matrixList.get(i); } return output; } }