LeetCode 矩阵置零（73题）

LeetCode 矩阵置零

@author:Jingdai
@date:2020.09.30

题目描述（73题）

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

• 示例输入：

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

• 示例输出：

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

思路

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

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

然后再遍历一遍数组，将对应的行和列中的元素都置为 0 ，即：

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

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

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

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

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

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

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

代码

public void setZeroes(int[][] matrix) {
        
    if (matrix.length == 0) {
        return;
    }

    boolean isRow = false;
    int row = matrix.length;
    int column = matrix[0].length;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
            if (i == 0) {
                if (matrix[i][j] == 0) {
                    isRow = true;
                }
            } else {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
    }

    for (int i = 1; i < row; i++) {
        for (int j = 1; j < column; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    if (matrix[0][0] == 0) {
        for (int i = 1; i < row; i++) {
            matrix[i][0] = 0;
        }
    }

    if (isRow) {
        for (int j = 0; j < column; j++) {
            matrix[0][j] = 0;
        }
    }
}