零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

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

示例 2：

输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

题目解法

解法 1

乍一看，这个问题似乎显而易见，直接遍历整个矩阵，只要发现值为0的元素，就将其所在的行和列清零。不过这种方法存在陷阱：在读取被清零的行或列时，读到的都是0，于是所在行和列都会变成0，很快，整个矩阵的所有元素都会变成0。

避开这个陷阱的方法之一是，新建一个矩阵，标记0元素位置，然后，在第二次遍历矩阵时，将0所在的行与列清零。这种做法的空间复杂度为O(MN)。

实际，不需要用矩阵存储，只需要用两个数组分别记录包含0元素的行和列即可，空间复杂度为O(N)。

算法实现（JAVA）

public class Solution {public void setZeroes(int[][] matrix) {boolean[] row = new boolean[matrix.length];boolean[] col = new boolean[matrix[0].length];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (matrix[i][j] == 0) {row[i] = true;col[j] = true;}}}// 置空行for (int i = 0; i < matrix.length; i++) {if (row[i]) {nullifyRow( matrix, i);}}// 置空列for (int j = 0; j < matrix[0].length; j++) {if (col[j]) {nullifyCol(matrix, j);}}}private void nullifyRow(int[][] matrix, int row) {for (int j = 0; j < matrix[0].length; j++) {matrix[row][j] = 0;}}private void nullifyCol(int[][] matrix, int col) {for (int i = 0; i < matrix.length; i++) {matrix[i][col] = 0;}}
}

解法 2

为了提高空间利用率，可以选用位向量替代布尔数组。通过使用矩阵的第一行代替解法1中的row数组，矩阵的第一列代替col数组，可以将算法的空间复杂度降为O(1)，具体步骤如下。

1. 检查第一行和第一列是否存在0元素，并根据结果设置rowHasZero和colHasZero的值。
2. 遍历矩阵其余元素，如果matrix[i][j]为0，则将matrix[i][0]和matrix[0][j]置为0。
3. 遍历矩阵中的其余元素，如果matrix[i][0]为0，则将第i行清零。
4. 遍历矩阵中的其余元素，如果matrix[0][j]为0，则将第j行清零。
5. 根据第1步的结果，如果需要则将第一行和第一列清零。

算法实现（JAVA）

public class Solution2 {public void setZeroes(int[][] matrix) {boolean rowHasZero = false;boolean colHasZero = false;// 检查第一行是否有0for (int j = 0; j < matrix[0].length; j++) {if (matrix[0][j] == 0) {rowHasZero = true;break;}}// 检查第一列是否有0for (int i = 0; i < matrix.length; i++) {if (matrix[i][0] == 0) {colHasZero = true;break;}}// 检查数组其余元素是否有0for (int i = 1; i < matrix.length; i++) {for (int j = 1; j < matrix[0].length; j++) {if (matrix[i][j] == 0) {matrix[i][0] = 0;matrix[0][j] = 0;}}}// 根据第一列的值置空行for (int i = 1; i < matrix.length; i++) {if (matrix[i][0] == 0) {nullifyRow(i, matrix);}}// 根据第一行的值置空列for (int j = 1; j < matrix[0].length; j++) {if (matrix[0][j] == 0) {nullifyCol(j, matrix);}}// 置空第一行if (rowHasZero) {nullifyRow(0, matrix);}// 置空第一列if (colHasZero) {nullifyCol(0, matrix);}}private void nullifyRow(int row, int[][] matrix) {for (int j = 0; j < matrix[0].length; j++) {matrix[row][j] = 0;}}private void nullifyCol(int col, int[][] matrix) {for (int i = 0; i < matrix.length; i++) {matrix[i][col] = 0;}}
}

[1] 盖尔.拉克曼.麦克道尔.程序员面试金典（第6版）[M].北京：人民邮电出版社，2019.9：167-169
[2] leetcode.面试题 01.08. 零矩阵