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

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

生活中的算法

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

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

问题描述

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

1. 输入：matrix = [
2.   [1,1,1],
3.   [1,0,1],
4.   [1,1,1]
5. ]
6. 输出：[
7.   [1,0,1],
8.   [0,0,0],
9.   [1,0,1]
10. ]

复制代码

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

就像在处理办公室防疫时，先用一张新表记录下所有需要检测的位置，然后统一处理。
让我们用一个简单的例子来理解：

1. 原矩阵：
2. [1,2,0]
3. [3,4,5]
5. 1. 记录0所在的位置：
6.    - 第0行，第2列有个0
8. 2. 标记需要置零的行和列：
9.    - 需要置零的行：[0]
10.    - 需要置零的列：[2]
12. 3. 根据记录修改矩阵：
13.    [0,0,0]  // 第0行全置零
14.    [3,4,0]  // 第2列置零

复制代码

优化解法：原地标记

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

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

示例演示

用下面的矩阵来说明：

1. [1,2,3]
2. [4,0,6]
3. [7,8,9]
5. 1. 记录第一行和第一列的状态：
6.    - 第一行没有0
7.    - 第一列没有0
9. 2. 用第一行和第一列标记：
10.    - 因为matrix[1][1]=0，所以：
11.      - 标记第一行：matrix[0][1]=0
12.      - 标记第一列：matrix[1][0]=0
14. 3. 根据标记处理矩阵主体：
15.    [1,0,3]
16.    [0,0,0]
17.    [7,0,9]
19. 4. 最后根据第一步的记录处理第一行第一列

复制代码

Java代码实现

1. public void setZeroes(int[][] matrix) {
2.     if (matrix == null || matrix.length == 0) return;
3.    
4.     int m = matrix.length;
5.     int n = matrix[0].length;
6.    
7.     // 记录第一行和第一列是否原本包含0
8.     boolean firstRowHasZero = false;
9.     boolean firstColHasZero = false;
10.    
11.     // 检查第一行
12.     for (int j = 0; j < n; j++) {
13.         if (matrix[0][j] == 0) {
14.             firstRowHasZero = true;
15.             break;
16.         }
17.     }
18.    
19.     // 检查第一列
20.     for (int i = 0; i < m; i++) {
21.         if (matrix[i][0] == 0) {
22.             firstColHasZero = true;
23.             break;
24.         }
25.     }
26.    
27.     // 使用第一行和第一列作为标记
28.     for (int i = 1; i < m; i++) {
29.         for (int j = 1; j < n; j++) {
30.             if (matrix[i][j] == 0) {
31.                 matrix[i][0] = 0;  // 标记该行
32.                 matrix[0][j] = 0;  // 标记该列
33.             }
34.         }
35.     }
36.    
37.     // 根据标记处理非第一行第一列的部分
38.     for (int i = 1; i < m; i++) {
39.         for (int j = 1; j < n; j++) {
40.             if (matrix[i][0] == 0 || matrix[0][j] == 0) {
41.                 matrix[i][j] = 0;
42.             }
43.         }
44.     }
45.    
46.     // 处理第一行
47.     if (firstRowHasZero) {
48.         for (int j = 0; j < n; j++) {
49.             matrix[0][j] = 0;
50.         }
51.     }
52.    
53.     // 处理第一列
54.     if (firstColHasZero) {
55.         for (int i = 0; i < m; i++) {
56.             matrix[i][0] = 0;
57.         }
58.     }
59. }

复制代码

解法比较

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

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

原地标记：

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

解题技巧总结

这道题给我们的启发：

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

类似的问题还有：

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

小结

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

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！