矩阵打印--蛇形遍历

给定一个矩阵,从第一个元素A[0][0]开始按左下↙️、右上↗、左下↙️、右上↗...类似蛇形状的顺序遍历,直到遍历完矩阵的所有元素,按遍历的顺序返回所有的元素
提示:矩阵不一定是方正
输入、输出描述
输入:
A:待遍历的矩阵
n:矩阵A的行数
m:矩阵A的列数

输出:
按蛇形状遍历矩阵的结果
Example
输入:
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;
  }
}
一个创业中的苦逼程序员
评论专区

隐藏