算法——之”字形打印矩阵

谁践踏了优雅 2022-04-18 01:50 183阅读 0赞

## 【题目】 ##

给定一个矩阵matrix，按照“之”字形的方式打印这 个矩阵，

例如: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)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70][]

### 思路： ###

使用宏观思想，千万不要把思路限制在局部。

①设计A，B指针一开始都在(0,0)位置

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 1][]

②A总是向右移动，B总是向下移动，当A运动到最右，往下移动，当B运动到最下，往右移动【A、B每次都走一步】，A和B每次都可以划出一个对角线。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 2][]       ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 3][]

最后A、B重合，我们只需要做的就是，通过A,B两个坐标，打印出对角线上的值，而之字型打印是有顺序的【左下到右上还是右上到左下】，我们只需要认为引入一个boolean量做区分即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 4][]

### 具体代码实现： ###

/**
     * 之字形打印
     */
    public class ZigZagPrint {
        public void printMatrixZigZag(int[][] matrix){
            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 != endR + 1){
                printLevel(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;
            }
            System.out.println();
        }
    
        private void printLevel(int[][] matrix, int aR, int aC, int bR, int bC, boolean fromUp) {
            if (fromUp) {
                while (aC != bC - 1) {
                    System.out.print(matrix[aR++][aC--] + " ");
                }
            } else {
                while (bC != aC + 1) {
                    System.out.print(matrix[bR--][bC++] + " ");
                }
            }
        }
    
        @Test
        public void test(){
            int[][] matrix = {
       {1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
            printMatrixZigZag(matrix);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70]: /images/20220418/f39f59360cfd426ab489316ca7ec5016.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 1]: /images/20220418/aa131d85abe94ea2a99172ffa81a56d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20181106202428949.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 3]: /images/20220418/0b7c391238d54c04b4f17b5693c529da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 4]: /images/20220418/c7720b7e93d045d785abae1096c490b7.png