每日算法：矩阵篇（在行列都排好序的矩阵中找数、“之”字形打印矩阵、旋转正方形矩阵、转圈打印矩阵）

秒速五厘米 2023-03-13 11:57 137阅读 0赞

## 1、转圈打印矩阵 ##

【题目】 给定一个整型矩阵matrix，请按照转圈的方式打印它。

例如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

打印结果为：1，2，3，4，8，12，16，15，14，13，9，5，6，7，11， 10，

【要求】 额外空间复杂度为O(1)

思路：我们定义两个点，一个是左上角a\[a\]\[b\]，一个是右下角a\[c\]\[d\]。坐标就是（a，b）、（c，d）。我们可以打印最外层的数，依次然后a、b都加1，c、d减一，进入内圈。

1    2     3    4

5                 8

9                12

13  14  15  16

然后是内圈：

5    6

10  11

public class Matrix {
    
    
        public static void spiralOrderPrint(int[][] matrix){
            int a = 0;
            int b = 0;
            int c = matrix.length - 1;
            int d = matrix[0].length - 1;
            while(a <= c && b <= d){
                printEdge(matrix,a++,b++,c--,d--);
            }
        }
    
        /**
         * 从左上角arr[a][b]到右下角arr[c][d]
         */
        public static void printEdge(int[][] arr,int a,int b,int c,int d){
            if(a == c){
                for(int i = b;i < d;i++){
                    System.out.print(arr[a][i] + " ");
                }
            }else if(b == d){
                for(int i = a;i < c;i++){
                    System.out.print(arr[i][b] + " ");
                }
            }else{
                int curR = a;
                int curC = b;
                while(curC != d){
                    System.out.print(arr[a][curC] + " ");
                    curC++;
                }
                while(curR != c){
                    System.out.print(arr[curR][d] + " ");
                    curR++;
                }
                while(curC != b){
                    System.out.print(arr[c][curC] + " ");
                    curC--;
                }
                while(curR != a ){
                    System.out.print(arr[curR][b] + " ");
                    curR--;
                }
            }
        }
    
        public static void main(String[] args) {
            int[][] matrix = { { 1, 2, 3, 4 },
                               { 5, 6, 7, 8 },
                               { 9, 10, 11, 12 },
                               { 13, 14, 15, 16 } };
            spiralOrderPrint(matrix);
    
        }
    }

## 2、旋转正方形矩阵 ##

【题目】 给定一个整型正方形矩阵matrix，请把该矩阵调整成

顺时针旋转90度的样子。

【要求】 额外空间复杂度为O(1)

思路：依然是有a、b、c、d的坐标

交换对应的节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

外圈遍历完，就可以进入内圈。

public class RotateMatrix {
    
        public static void rotateEdge(int[][] arr,int a,int b,int c,int d){
            int times = c - a;
            int temp = 0;
            for(int i = 0; i != times;i++){
                temp = arr[a][b + i];
                arr[a][b + i] = arr[c - i][b];
                arr[c - i][b] = arr[c][d - i];
                arr[c][d - i] = arr[a + i][d];
                arr[a + i][d] = temp;
            }
        }
    
        public static void rotate(int[][] matrix){
            int a = 0;
            int b = 0;
            int c = matrix.length - 1;
            int d = matrix[0].length - 1;
            while(a < c){
                rotateEdge(matrix,a++,b++,c--,d--);
            }
        }
    
        public static void printMatrix(int[][] matrix) {
            for (int i = 0; i != matrix.length; i++) {
                for (int j = 0; j != matrix[0].length; j++) {
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
        }
        public static void main(String[] args) {
            int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
                    { 13, 14, 15, 16 } };
            printMatrix(matrix);
            rotate(matrix);
            System.out.println("=========");
            printMatrix(matrix);
    
        }
    }

## 3、“之”字形打印矩阵 ##

【题目】 给定一个矩阵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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2][]

这个就有点像以对角线打印输出数据，打印的方向我们可以用一个boolean类型来控制，我们先设置两个点x(a,b)，y(c,d)。起初都是指向1。然后我们有一个规则。

x点向右移动，如果到边界了，就向下移动。

y点向下移动，如果到边界了，就向右移动。

public class zhiziprint {
    
        public static void printMatrixZigZag(int[][] matrix) {
            int a = 0;
            int b = 0;
            int c = 0;
            int d = 0;
            int endR = matrix.length - 1;
            int endC = matrix[0].length - 1;
            boolean flag = false;
            while (a != endR + 1) {
                printLevel(matrix, a, b, c, d, flag);
                //arr[a][b]，移动，这个点只向右移动，如果到头了，向下。
                a = b == endC ? a + 1 : a;
                b = b == endC ? b : b + 1;
                //arr[c][d]，移动，这个点只向下移动，如果到头了，向右。
                d = c == endR ? d + 1 : d;
                c = c == endR ? c : c + 1;
                flag = !flag;
            }
            System.out.println();
        }
    
        public static void printLevel(int[][] arr, int a, int b, int c, int d, boolean flag) {
            if (flag) {
                while (a != c + 1) {
                    System.out.print(arr[a++][b--] + " ");
                }
            } else {
                while(c != a - 1){
                    System.out.print(arr[c--][d++] + " ");
                }
            }
        }
    
        public static void main(String[] args) {
            int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
            printMatrixZigZag(matrix);
    
        }
    
    }

## 4、在行列都排好序的矩阵中找数 ##

【题目】 给定一个有N\*M的整型矩阵matrix和一个整数K，matrix的每一行和每一 列都是排好序的。实现一个函数，判断K

是否在matrix中。 例如： 0 1 2 5 2 3 4 7 44 4 8 5 7 7 9 如果K为7，返回true；如果K为6，返回false。

【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)。

思路：我们采用从右上角开始查找。

1    3     5      6

2    5     7      9

4    6     8     10

我们指针指向6开始查找如果指向的数比要查找的数大，那么指向的数下面的一列就都不存在满足条件的了。那么指针向左移动。

如果指向的数比要查找的数小那么所在行就都可以抛弃了，然后向下移动。最后就能找到要查找的数，或者没找到。

public class FindMatrix {
    
        public static boolean findNum(int[][] arr,int num){
            //a、b是右上角两个数
            int a = 0;
            int b = arr[0].length - 1;
            int len = arr.length;
    
            while( a <= len - 1 && b >= 0){
                if(arr[a][b] > num){
                    b--;
                }else if(arr[a][b] < num){
                    a++;
                }else{
                    return true;
                }
            }
            return false;
    
        }
    
        public static void main(String[] args) {
            int[][] matrix = { { 1, 3, 5,6 }, { 2,5,7,9}, {4,6,8,10 }};
            System.out.println(findNum(matrix,6));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: /images/20230312/a10ee55f2bda4960b2466c7ea7e42d26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: /images/20230312/5e771c69a40141b685b65ae95f890974.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200513153900429.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70