LeetCode矩阵置零（73题）

&＃64;author:Jingdai
&＃64;date:2020.09.30

题目描述&＃xff08;73题&＃xff09;

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

• 示例输入&＃xff1a;

[[1,1,1],[1,0,1],[1,1,1]
]


• 示例输出&＃xff1a;

[[1,0,1],[0,0,0],[1,0,1]
]


思路

看到题目&＃xff0c;第一想法应该是使用两个集合分别记录哪些行和哪些列应该设置为0&＃xff0c;当遍历到 matrix[i][j] 时&＃xff0c;如果它等于 0 &＃xff0c;则在行集合中加入 i &＃xff0c;在列集合中加入 j &＃xff0c;即:

if (matrix[i][j] &＃61;&＃61; 0) {rowSet.add(i);columnSet.add(j);
}


然后再遍历一遍数组&＃xff0c;将对应的行和列中的元素都置为 0 &＃xff0c;即&＃xff1a;

if (rowSet.contains(i) || columnSet.contains(j)) {matrix[i][j] &＃61; 0;
}


这种方法比较直观&＃xff0c;也好理解&＃xff0c;但是需要一个额外的(m&＃43;n) 大小的空间&＃xff0c;这里使用另一种方法&＃xff0c;仅使用常量大小的空间。

按上面方法的思路&＃xff0c;我们需要记录哪一行和哪一列需要设置为 0 &＃xff0c;我们可以利用矩阵第 0 行和第 0 列的元素来记录&＃xff0c;如下图&＃xff1a;

当 matrix[1][1] 等于 0 时&＃xff0c;就将它对应的行的首元素 matrix[1][0] 和对应列的首元素 matrix[0][1] 置为 0 &＃xff0c;这里注意到将对应的行和列的首元素置为 0 并不会影响之后的判断&＃xff0c;因为你会发现遍历矩阵时&＃xff0c; matrix[i][j] 永远在 matrix[0][j] 和 matrix[i][0] 的后面&＃xff0c;所以不会影响到之后的判断。遍历完整个矩阵后&＃xff0c;再次遍历矩阵&＃xff0c;将第 0 行中 0 元素对应的列全部置 0 &＃xff0c;将第 0 列中 0 元素对应的行全部置 0 。

好像这样就完了&＃xff0c;但是其实有一个问题&＃xff0c;看下图。

当 0 元素位于第 0 行或第 0 列时&＃xff0c;如图中的 matrix[1][0] 和 matrix[0][1] &＃xff0c;都会使 matrix[0][0] 变为 0 &＃xff0c;无法判断是第 0 行有 0 元素还是第 0 列有 0 元素&＃xff0c;所以我们需要多余的变量记录第 0 行和第 0 列是否有 0 元素。

这里我们多设置一个 boolean 变量 isRow&＃xff0c; 记录了第 0 行是否有零元素&＃xff0c;在遍历第 0 行时&＃xff0c;我们不修改 matrix 的值&＃xff0c;如果第 0 行包含 0 &＃xff0c;就将 isRow 设置为 true &＃xff0c;其它和之前一样&＃xff0c;而如果最后 matrix[0][0] 值为 0 &＃xff0c;则肯定是第 0 列包含 0 &＃xff08;或者它本身是 0&＃xff0c;本身也在第 0 列&＃xff09;&＃xff0c;然后第二次遍历修改的时候先不修改第 0 行和第 0 列&＃xff0c;之后根据 isRow 和 matrix[0][0] 的值来单独更新第 0 行和第 0 列。代码如下。

代码

public void setZeroes(int[][] matrix) {if (matrix.length &＃61;&＃61; 0) {return;}boolean isRow &＃61; false;int row &＃61; matrix.length;int column &＃61; matrix[0].length;for (int i &＃61; 0; i < row; i&＃43;&＃43;) {for (int j &＃61; 0; j < column; j&＃43;&＃43;) {if (i &＃61;&＃61; 0) {if (matrix[i][j] &＃61;&＃61; 0) {isRow &＃61; true;}} else {if (matrix[i][j] &＃61;&＃61; 0) {matrix[i][0] &＃61; 0;matrix[0][j] &＃61; 0;}}}}for (int i &＃61; 1; i < row; i&＃43;&＃43;) {for (int j &＃61; 1; j < column; j&＃43;&＃43;) {if (matrix[i][0] &＃61;&＃61; 0 || matrix[0][j] &＃61;&＃61; 0) {matrix[i][j] &＃61; 0;}}}if (matrix[0][0] &＃61;&＃61; 0) {for (int i &＃61; 1; i < row; i&＃43;&＃43;) {matrix[i][0] &＃61; 0;}}if (isRow) {for (int j &＃61; 0; j < column; j&＃43;&＃43;) {matrix[0][j] &＃61; 0;}}
}