73. 矩阵置零#

生活中的算法#

想象你在玩扫雷游戏，当你点到一个地雷时，不仅这个格子会被标记，与它同行同列的格子也都会受到影响。或者想象一个办公室的座位表，如果某个位置发现了感染者，为了安全起见，需要将该员工所在的整行（同排同事）和整列（对面同事）都标记为密切接触者需要检测。

这种”一点触发，全行全列响应”的场景在生活中很常见：

学校课程表中，如果某个老师请假，那一整行的课程都需要调整
表格处理软件中，调整某个单元格的格式，可以统一设置整行整列
影院选座系统中，如果一个座位损坏，可能需要锁定那一排和那一列的预订功能

问题描述#

题目目标#

LeetCode第73题”矩阵置零”是这样描述的：给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1#

输入：

matrix = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

text

输出：

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

text

矩阵示意：

1 1 1
1 0 1
1 1 1

text

说明： 图示把输入结构和输出结果并排展开后，会更容易直接看清题目的变化过程。

补充说明#

矩阵按行给出，外层数组表示所有行，内层数组表示每一行的元素。

最直观的解法：额外空间标记#

就像在处理办公室防疫时，先用一张新表记录下所有需要检测的位置，然后统一处理。

让我们用一个简单的例子来理解：

原矩阵：
[1,2,0]
[3,4,5]

1. 记录0所在的位置：
   - 第0行，第2列有个0

2. 标记需要置零的行和列：
   - 需要置零的行：[0]
   - 需要置零的列：[2]

3. 根据记录修改矩阵：
   [0,0,0]  // 第0行全置零
   [3,4,0]  // 第2列置零

plaintext

优化解法：原地标记#

仔细思考会发现，我们可以用矩阵的第一行和第一列来记录标记信息，就像用办公室的墙上的记事板来标记需要处理的区域。这样就不需要额外的空间了。

原地标记的原理#

先记录第一行和第一列是否原本包含0
用第一行和第一列作为标记板
处理剩余的矩阵
最后根据第一步的记录处理第一行和第一列

示例演示#

用下面的矩阵来说明：

[1,2,3]
[4,0,6]
[7,8,9]

1. 记录第一行和第一列的状态：
   - 第一行没有0
   - 第一列没有0

2. 用第一行和第一列标记：
   - 因为matrix[1][1]=0，所以：
     - 标记第一行：matrix[0][1]=0
     - 标记第一列：matrix[1][0]=0

3. 根据标记处理矩阵主体：
   [1,0,3]
   [0,0,0]
   [7,0,9]

4. 最后根据第一步的记录处理第一行第一列

plaintext

Java代码实现#

public void setZeroes(int[][] matrix) {
    // 边界条件：如果矩阵为空或没有任何行，直接返回，避免后续访问越界
    if (matrix == null || matrix.length == 0) return;

    // m 表示矩阵的行数
    int m = matrix.length;
    // n 表示矩阵的列数（题目保证矩阵至少有一行，所以 matrix[0] 可访问）
    int n = matrix[0].length;

    // firstRowHasZero：记录“原始第一行”中是否出现过 0
    // 之所以要单独记录，是因为第一行后面会被当作标记区使用
    boolean firstRowHasZero = false;
    // firstColHasZero：记录“原始第一列”中是否出现过 0
    // 同理，第一列也会被复用为标记区，原始信息需要提前保存
    boolean firstColHasZero = false;

    // 第一步：扫描第一行，判断原始第一行是否需要最终置零
    for (int j = 0; j < n; j++) {
        // 只要第一行有一个 0，就说明第一行最终必须全部变成 0
        if (matrix[0][j] == 0) {
            firstRowHasZero = true;
            // 已确认后可以提前结束扫描，减少无效遍历
            break;
        }
    }

    // 第二步：扫描第一列，判断原始第一列是否需要最终置零
    for (int i = 0; i < m; i++) {
        // 只要第一列有一个 0，就说明第一列最终必须全部变成 0
        if (matrix[i][0] == 0) {
            firstColHasZero = true;
            // 已确认后可以提前结束扫描
            break;
        }
    }

    // 第三步：从 (1,1) 开始遍历矩阵主体（跳过第一行和第一列）
    // 若 matrix[i][j] 为 0，则把该行行首和该列列首置为 0，作为“标记”
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            // 发现一个 0，就标记“整行要清零、整列要清零”
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;  // 标记该行
                matrix[0][j] = 0;  // 标记该列
            }
        }
    }

    // 第四步：再次遍历矩阵主体，根据标记执行真正的置零
    // 规则：只要当前行被标记 或 当前列被标记，当前位置就置为 0
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            // matrix[i][0] == 0 表示第 i 行需要清零
            // matrix[0][j] == 0 表示第 j 列需要清零
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // 第五步：根据最初记录，决定是否清零第一行
    // 注意必须放在最后处理，否则会破坏前面用到的标记信息
    if (firstRowHasZero) {
        for (int j = 0; j < n; j++) {
            // 将第一行每个元素置为 0
            matrix[0][j] = 0;
        }
    }

    // 第六步：根据最初记录，决定是否清零第一列
    if (firstColHasZero) {
        for (int i = 0; i < m; i++) {
            // 将第一列每个元素置为 0
            matrix[i][0] = 0;
        }
    }
}

java

解法比较#

让我们比较这两种方法：

额外空间标记：

时间复杂度：O(m×n)
空间复杂度：O(m+n)
优点：思路清晰，实现简单
缺点：需要额外空间

原地标记：

时间复杂度：O(m×n)
空间复杂度：O(1)
优点：不需要额外空间
缺点：实现稍复杂，需要额外记录第一行列的状态

解题技巧总结#

这道题给我们的启发：

矩阵问题中，往往可以利用矩阵本身来存储信息
处理特殊情况（如第一行列）时，可以单独考虑
分步骤处理复杂问题可以让思路更清晰
在修改数据时，注意保护原始信息

类似的问题还有：

生命游戏
旋转图像
岛屿数量

小结#

通过矩阵置零这道题，我们学会了如何巧妙地利用矩阵本身来存储信息，避免使用额外空间。这种思维方式不仅适用于本题，在处理需要原地修改数据的矩阵问题时都很有启发。记住，当遇到需要在矩阵中标记信息的问题时，考虑能否利用矩阵本身的某些位置来存储标记！