【忍者算法】从扫雷游戏到矩阵操作：探索矩阵置零问题｜LeetCode 73 矩阵置零
从扫雷游戏到矩阵操作：探索矩阵置零问题生活中的算法
想象你在玩扫雷游戏，当你点到一个地雷时，不仅这个格子会被标记，与它同行同列的格子也都会受到影响。或者想象一个办公室的座位表，如果某个位置发现了感染者，为了安全起见，需要将该员工所在的整行（同排同事）和整列（对面同事）都标记为密切接触者需要检测。
这种"一点触发，全行全列响应"的场景在生活中很常见：
[*]学校课程表中，如果某个老师请假，那一整行的课程都需要调整
[*]表格处理软件中，调整某个单元格的格式，可以统一设置整行整列
[*]影院选座系统中，如果一个座位损坏，可能需要锁定那一排和那一列的预订功能
问题描述
LeetCode第73题"矩阵置零"是这样描述的：给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
例如：
输入：matrix = [,,]输出：[,,]最直观的解法：额外空间标记
就像在处理办公室防疫时，先用一张新表记录下所有需要检测的位置，然后统一处理。
让我们用一个简单的例子来理解：
原矩阵：1. 记录0所在的位置： - 第0行，第2列有个02. 标记需要置零的行和列： - 需要置零的行： - 需要置零的列：3. 根据记录修改矩阵： // 第0行全置零 // 第2列置零优化解法：原地标记
仔细思考会发现，我们可以用矩阵的第一行和第一列来记录标记信息，就像用办公室的墙上的记事板来标记需要处理的区域。这样就不需要额外的空间了。
原地标记的原理
[*]先记录第一行和第一列是否原本包含0
[*]用第一行和第一列作为标记板
[*]处理剩余的矩阵
[*]最后根据第一步的记录处理第一行和第一列
示例演示
用下面的矩阵来说明：
1. 记录第一行和第一列的状态： - 第一行没有0 - 第一列没有02. 用第一行和第一列标记： - 因为matrix=0，所以： - 标记第一行：matrix=0 - 标记第一列：matrix=03. 根据标记处理矩阵主体： 4. 最后根据第一步的记录处理第一行第一列Java代码实现
public void setZeroes(int[][] matrix) { if (matrix == null || matrix.length == 0) return; int m = matrix.length; int n = matrix.length; // 记录第一行和第一列是否原本包含0 boolean firstRowHasZero = false; boolean firstColHasZero = false; // 检查第一行 for (int j = 0; j < n; j++) { if (matrix == 0) { firstRowHasZero = true; break; } } // 检查第一列 for (int i = 0; i < m; i++) { if (matrix == 0) { firstColHasZero = true; break; } } // 使用第一行和第一列作为标记 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix == 0) { matrix = 0;// 标记该行 matrix = 0;// 标记该列 } } } // 根据标记处理非第一行第一列的部分 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix == 0 || matrix == 0) { matrix = 0; } } } // 处理第一行 if (firstRowHasZero) { for (int j = 0; j < n; j++) { matrix = 0; } } // 处理第一列 if (firstColHasZero) { for (int i = 0; i < m; i++) { matrix = 0; } }}解法比较
让我们比较这两种方法：
额外空间标记：
[*]时间复杂度：O(m×n)
[*]空间复杂度：O(m+n)
[*]优点：思路清晰，实现简单
[*]缺点：需要额外空间
原地标记：
[*]时间复杂度：O(m×n)
[*]空间复杂度：O(1)
[*]优点：不需要额外空间
[*]缺点：实现稍复杂，需要额外记录第一行列的状态
解题技巧总结
这道题给我们的启发：
[*]矩阵问题中，往往可以利用矩阵本身来存储信息
[*]处理特殊情况（如第一行列）时，可以单独考虑
[*]分步骤处理复杂问题可以让思路更清晰
[*]在修改数据时，注意保护原始信息
类似的问题还有：
[*]生命游戏
[*]旋转图像
[*]岛屿数量
小结
通过矩阵置零这道题，我们学会了如何巧妙地利用矩阵本身来存储信息，避免使用额外空间。这种思维方式不仅适用于本题，在处理需要原地修改数据的矩阵问题时都很有启发。记住，当遇到需要在矩阵中标记信息的问题时，考虑能否利用矩阵本身的某些位置来存储标记！
<hr>作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
完整GitHub项目
页:
[1]