之字型打印矩阵

发表于 | 分类于

题目描述

之字形打印一个矩阵

之字形

例如：

1 2 3 4
5 6 7 8
9 10 11 12

打印结果是1, 2,5, 9,6,3, 4,7,10, 11,8, 12。
要求额外空间复杂度是O(1)

分析

思路

两个坐标进行记录，都从0,0点开始。一个往右移动，移动到最右往下移动；另一个往下移动，移动到最下往右移动，两个坐标始终处于一条斜线，然后打印斜线上的元素就行。

做法

宏观调度

设置两个点A(aR,aC),B(bR,bC)（行，列），都从0,0点开始。

  • 宏观
    A向右走，当到最右点的时候（走过了 endC = matrix[0].length-1列），向下走
    B向下走，当到最下点的时候（走过了 endR = matrix.length-1行），向右走
  • 打印方向
    设置一个布尔变量表示从上到下还是从下到上打印
  • 结束
    当aR到最后一行的时候 或者 当bC到最后一列的时候标志着打印结束

二维数组

二维数组其实是由一维数组组成，比如

1
2
3
4
int[][] arr = {
		{1,2,3,4},
		{4,5,6,8}
	  };

int rows = i.length;//行数
int columns = i[0].length;//列数

  • length就是行数
  • 列数是具体到其中的一维里面，再求length

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class ZigZagPrintMatrix {
    public static void zigZagPrintMatrix(int[][]matrix){
        if(matrix==null || matrix.length==0 || matrix[0].length==0){
            return ;
        }
        int aR = 0;//行
        int aC = 0;//列
        int bR = 0;//行
        int bC = 0;//列
        int endR = matrix.length-1;//行结束位置，的索引
        int endC = matrix[0].length-1;//列结束位置，的索引
        boolean fromUp = false;
        while(aR != matrix.length){//当aR到最后一行的时候 
            printMatrix(matrix, aR, aC, bR, bC, fromUp);
            aR = aC==endC ? aR+1 : aR;
            aC = aC==endC ? aC : aC+1;
            bC = bR==endR ? bC+1 : bC;
            bR = bR==endR ? bR : bR+1;
            fromUp = !fromUp;
        }
    }

    public static void printMatrix(int[][]matrix,int aR,int aC,
                                int bR,int bC,boolean fromUp){
        if(fromUp){//从右上到左下
            while(aR!= bR+1){//一行一行扫过来
                System.out.print(matrix[aR++][aC--]+" ");
            }
        }else {
            while(bR != aR-1){
                System.out.print(matrix[bR--][bC++]+" ");
            }
        }
    }
    public static void main(String[] args) {
        int matrix[][] = new int[][]{
            {1, 2, 3,  4},
            {5, 6, 7,  8},
            {9, 10,11, 12},
            {13,14,15, 16}
        };
        zigZagPrintMatrix(matrix);
    }
}

输出

> >