矩阵-矩阵置零

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 在计算机科学中，一个原地算法（in-place algorithm）是一种使用小的，固定数 量的额外之空间来转换资料的算法。当算法执行时，输入的资料通常会被要输出的部 分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所 （out-of-place）。

输入：二维数组 输出：二维数组 思路：

方法一：使用两个标记数组 两个标记数组分别记录每一行和每一列是否有零出现，如果出现，则将对应的标记数组置为true，最后再次遍历数组，用标记数组更新原数组即可

class Solution { public void setZeroes(int[][] matrix) { //用变量定义数组的行和列的长度，方便写代码 int m = matrix.length; int n = matrix[0].length; //定义标记数组 boolean [] row = new boolean[m]; boolean [] col = new boolean[n]; //对标记数组进行赋值 for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(matrix[i][j] == 0){ row[i] = col[j] = true; } } } //再次遍历,只要有一个标记为true，则置为0 for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(row[i] || col[j]){ matrix[i][j] = 0; } } } } }

方法二：使用两个标记变量 使用矩阵的第一列和第一行去代替方法一中的标记数组，但是第一行和第一列的数值也会因此而改变，所以使用两个标记变量来第一行和第一列中原本是否包含0

class Solution { public void setZeroes(int[][] matrix) { //用变量定义数组的行和列的长度，方便写代码 int m = matrix.length; int n = matrix[0].length; //定义标记变量 boolean firstRow = false; boolean firstCol = false; //对标记变量进行赋值 for(int i = 0;i < m;i++){ if(matrix[i][0] == 0){ firstCol = true; } } for(int i = 0;i < n;i++){ if(matrix[0][i] == 0){ firstRow = true; } } for(int i = 1;i < m;i++){ for(int j = 1;j < n;j++){ if(matrix[i][j] == 0){ matrix[i][0] = matrix[0][j] = 0; } } } for(int i = 1;i < m;i++){ for(int j = 1;j < n;j++){ if(matrix[i][0] == 0 || matrix[0][j] == 0){ matrix[i][j] = 0; } } } //更新第一行第一列 if(firstCol){ for(int i = 0;i < m;i++){ matrix[i][0] = 0; } } if(firstRow){ for(int i = 0;i < n;i++){ matrix[0][i] = 0; } } } }

方法三：使用一个标记变量 第一列的第一个元素即可以标记第一行是否出现0。但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。

class Solution { public void setZeroes(int[][] matrix) { //用变量定义数组的行和列的长度，方便写代码 int m = matrix.length; int n = matrix[0].length; //定义标记变量 boolean firstColAndRow = false; //对标记变量进行赋值 for(int i = 0; i < m; i++){ if(matrix[i][0] == 0){ firstColAndRow = true; } for(int j = 1; j < n; j++){ if(matrix[i][j] == 0){ matrix[i][0] = matrix[0][j] = 0; } } } //倒序 for(int i = m - 1; i >= 0; i--){ for(int j = 1; j < n; j++){ if(matrix[i][0] == 0 || matrix[0][j] == 0){ matrix[i][j] = 0; } } if(firstColAndRow){ matrix[i][0] = 0; } } } }