【LeetCode】算法详解#7 ---矩阵置零

1.题目介绍

        给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

2.解决思路

        这是一个很容易解决的问题，给定一个矩阵，将为0位置的行和列都标记为0。矩阵可以看做是二维数组，如果[i][j]位置为0，那么只需要将从[i][0~length]和[0~length][j]的所有元素都标记为0即可。但是存在一个问题，扫描时按照行扫描，如果碰到一个为0的位置，将行和列都标记为0。那么后续遍历到被标记为零的位置时，则会触发错误的判定，导致结果错误。所以需要将原矩阵保存一个副本，原矩阵用来判断0的位置，副本矩阵用来实际进行置零操作，最终再将副本复制到原矩阵。

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

 3.步骤讲解

        1.定义矩阵行数m和列数n，矩阵的长度(二维数组中一维数组的数量)为行数，二维数组中任意一个一维数组的长度为列数。

        2.保存一份矩阵的副本copy，由于是二维数组，所以需要遍历拷贝。

        3.对原二维数组进行遍历，如果遇到某个位置值为0，则进行置零操作

        4.定义工具方法，传入数组副本，为零位置的坐标以及矩阵的长和宽，在其中分别进行行和列的置零操作，行置零时，列不变；列置零时，行不变。

        5.最终数组副本就是最终结果，再次利用拷贝将副本数组的值拷贝到原数组

 4.代码展示

public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        //数组副本
        int[][] copy = new int[m][];
        for (int i = 0; i < m; i++) {
            copy[i] = Arrays.copyOf(matrix[i], n);
        }
        //对原数组做遍历
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0){
                    //对副本数组做更改
                    util(copy,  i, j,m,n);
                }
            }
        }
        for (int i = 0; i < m; i++){
            matrix[i] = Arrays.copyOf(copy[i], n);
        }
    }

    public static void util(int[][] copy,  int m, int n,int mLength,  int nLength) {
        for (int i = 0; i < mLength; i++){
            copy[i][n] = 0;
        }
        for (int j = 0; j < nLength; j++){
            copy[m][j] = 0;
        }
    }
}

5.执行结果

在leetcode中测试用例平均耗时1ms

 内存分布44.67MB