题目描述
LeetCode 73. 矩阵置零
给定一个m x n的矩阵，如果一个元素为0，则将其所在行和列的所有元素都设为0。请使用原地算法。
示例 1：
text
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
text
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？
解题思路
这道题最大的坑点在于：如果在遍历过程中直接修改矩阵，新赋值的0会影响后续判断，导致整个矩阵全变成0。因此，我们需要采取"先标记，后修改"的策略。
下面介绍三种解法，从最容易想到到最节省空间，逐步优化。
解法一：标记数组（O(m+n) 空间）
思路
这是最直观的解法。我们创建两个布尔数组：row和col，分别记录每一行和每一列是否需要被置零。
第一次遍历矩阵，如果
matrix[i][j] == 0，则将row[i]和col[j]都标记为true。第二次遍历矩阵，如果
row[i]或col[j]为true，则将当前位置置为 0。
代码实现
java
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean[] row = new boolean[m]; boolean[] col = new boolean[n]; // 第一次遍历：记录哪些行和列需要置零 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { row[i] = true; col[j] = true; } } } // 第二次遍历：根据标记置零 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (row[i] || col[j]) { matrix[i][j] = 0; } } } } }复杂度分析
时间复杂度：O(m × n)，需要遍历两次矩阵。
空间复杂度：O(m + n)，需要两个额外数组。
解法二：两个标记变量（O(1) 空间，优化版）
思路
能不能不使用额外数组？我们可以利用矩阵的第一行和第一列来存储标记信息。
具体做法：
用两个布尔变量
rowZero和colZero记录第一行和第一列本身是否原本包含 0。从
(1,1)位置开始遍历，如果matrix[i][j] == 0，则将matrix[i][0]和matrix[0][j]标记为 0。第二次遍历（从
(1,1)开始），如果matrix[i][0] == 0或matrix[0][j] == 0，则将当前位置置为 0。最后根据
rowZero和colZero决定是否将第一行和第一列置为 0。
为什么要单独记录第一行和第一列？
因为第一行和第一列同时承担了"存储标记"的角色，它们原本的状态会被覆盖。如果不提前记录，我们就不知道第一行和第一列本身是否需要被置零。
代码实现
java
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean rowZero = false, colZero = false; // 1. 记录第一行和第一列是否原本包含 0 for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) colZero = true; } for (int j = 0; j < n; j++) { if (matrix[0][j] == 0) rowZero = true; } // 2. 使用第一行和第一列作为标记 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // 3. 根据标记置零（从 (1,1) 开始） for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } // 4. 最后处理第一行和第一列 if (rowZero) { for (int j = 0; j < n; j++) matrix[0][j] = 0; } if (colZero) { for (int i = 0; i < m; i++) matrix[i][0] = 0; } } }复杂度分析
时间复杂度：O(m × n)
空间复杂度：O(1)
解法三：一个标记变量（极简版）
思路
能否进一步优化，只用一个标记变量？答案是肯定的。
我们只用colZero记录第一列是否包含 0，而第一行是否包含 0 的信息可以存储在matrix[0][0]中。
但这里有一个关键细节：置零操作需要从最后一行开始倒序进行。因为matrix[0][0]既代表第一行的状态，也代表第一列的状态，如果正序处理，第一行的状态可能会被提前覆盖。
代码实现
java
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean colZero = false; for (int i = 0; i < m; i++) { // 检查第一列是否有 0 if (matrix[i][0] == 0) colZero = true; // 检查其他列，并将标记存储在第一行和第一列 for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // 倒序遍历，避免标记被覆盖 for (int i = m - 1; i >= 0; i--) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } if (colZero) { matrix[i][0] = 0; } } } }复杂度分析
时间复杂度：O(m × n)
空间复杂度：O(1)
三种解法对比
| 解法 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|
| 标记数组 | O(m+n) | 简单直观，不易出错 | 需要额外空间 |
| 两个标记变量 | O(1) | 空间最优，思路清晰 | 需要单独记录第一行/列 |
| 一个标记变量 | O(1) | 最节省空间 | 倒序遍历容易写错，可读性略差 |
推荐：面试时建议先给出解法一，然后主动优化到解法二，这样能展示你的优化思维。解法三可以作为扩展了解，实际工程中更推荐解法二，因为可读性更好。
踩坑提醒
不要边遍历边置零：这是最常见的错误。如果遇到 0 就立即将整行整列置零，后面遍历到的 0 可能是刚被赋值的，会导致错误地多置零。
注意第一行和第一列的特殊性：当使用原地标记法时，一定要先记录第一行和第一列的原始状态，否则它们的状态会丢失。
考虑边界情况：如果矩阵只有一行或一列，确保代码仍然能正确运行。
总结
这道题的核心思想是"标记后置"—— 先记录哪些行/列需要置零，再进行修改。从 O(mn) 到 O(m+n) 再到 O(1) 的空间优化过程，是一道非常经典的考察原地算法的题目。
掌握这三种解法，不仅能帮你通过这道题，更能让你对矩阵操作类的题目有更深的理解。
题目链接 & 题解链接
题目链接：LeetCode 73. 矩阵置零
本题题解链接：LeetCode 官方题解 - 矩阵置零
如果这篇文章对你有帮助，欢迎点赞、收藏、关注！更多 LeetCode HOT 100 题解持续更新中～
