【忍者算法】从扫雷游戏到矩阵操作：探索矩阵置零问题｜LeetCode 73 矩阵置零

lxl

从扫雷游戏到矩阵操作：探索矩阵置零问题

生活中的算法

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

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

问题描述

LeetCode第73题"矩阵置零"是这样描述的：给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
例如：
输入：matrix = [  [1,1,1],  [1,0,1],  [1,1,1]]输出：[  [1,0,1],  [0,0,0],  [1,0,1]]最直观的解法：额外空间标记

就像在处理办公室防疫时，先用一张新表记录下所有需要检测的位置，然后统一处理。
让我们用一个简单的例子来理解：
原矩阵：[1,2,0][3,4,5]1. 记录0所在的位置：   - 第0行，第2列有个02. 标记需要置零的行和列：   - 需要置零的行：[0]   - 需要置零的列：[2]3. 根据记录修改矩阵：   [0,0,0]  // 第0行全置零   [3,4,0]  // 第2列置零优化解法：原地标记

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

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

示例演示

用下面的矩阵来说明：
[1,2,3][4,0,6][7,8,9]1. 记录第一行和第一列的状态：   - 第一行没有0   - 第一列没有02. 用第一行和第一列标记：   - 因为matrix[1][1]=0，所以：     - 标记第一行：matrix[0][1]=0     - 标记第一列：matrix[1][0]=03. 根据标记处理矩阵主体：   [1,0,3]   [0,0,0]   [7,0,9]4. 最后根据第一步的记录处理第一行第一列Java代码实现

public void setZeroes(int[][] matrix) {    if (matrix == null || matrix.length == 0) return;        int m = matrix.length;    int n = matrix[0].length;        // 记录第一行和第一列是否原本包含0    boolean firstRowHasZero = false;    boolean firstColHasZero = false;        // 检查第一行    for (int j = 0; j < n; j++) {        if (matrix[0][j] == 0) {            firstRowHasZero = true;            break;        }    }        // 检查第一列    for (int i = 0; i < m; i++) {        if (matrix[0] == 0) {            firstColHasZero = true;            break;        }    }        // 使用第一行和第一列作为标记    for (int i = 1; i < m; i++) {        for (int j = 1; j < n; j++) {            if (matrix[j] == 0) {                matrix[0] = 0;  // 标记该行                matrix[0][j] = 0;  // 标记该列            }        }    }        // 根据标记处理非第一行第一列的部分    for (int i = 1; i < m; i++) {        for (int j = 1; j < n; j++) {            if (matrix[0] == 0 || matrix[0][j] == 0) {                matrix[j] = 0;            }        }    }        // 处理第一行    if (firstRowHasZero) {        for (int j = 0; j < n; j++) {            matrix[0][j] = 0;        }    }        // 处理第一列    if (firstColHasZero) {        for (int i = 0; i < m; i++) {            matrix[0] = 0;        }    }}解法比较

让我们比较这两种方法：
额外空间标记：

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

原地标记：

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

解题技巧总结

这道题给我们的启发：

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

类似的问题还有：

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

小结

通过矩阵置零这道题，我们学会了如何巧妙地利用矩阵本身来存储信息，避免使用额外空间。这种思维方式不仅适用于本题，在处理需要原地修改数据的矩阵问题时都很有启发。记住，当遇到需要在矩阵中标记信息的问题时，考虑能否利用矩阵本身的某些位置来存储标记！
<hr>作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
完整GitHub项目