千问 LeetCode 73. 矩阵置零 Java实现

这道题的核心考点是「原地算法」（In-place Algorithm），即在不使用额外矩阵空间的前提下完成修改。

核心思路：复用首行首列作为标记

最直观的解法是用两个数组记录哪些行、哪些列需要置零，但这需要 O(m+n) 的额外空间。为了达到 O(1) 的空间复杂度，我们可以复用矩阵的第一行和第一列来充当标记数组。

具体步骤如下：

Java 代码实现

class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;

// 1. 检查首行和首列是否原本就包含 0
boolean firstRowZero = false;
boolean firstColZero = false;

for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}

// 2. 遍历内部矩阵，利用首行首列作为标记
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0; // 标记第 i 行需要置零
matrix[0][j] = 0; // 标记第 j 列需要置零
}
}
}

// 3. 根据标记，将内部矩阵对应的行列置零
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 (firstRowZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (firstColZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}

}

复杂度分析

• 时间复杂度：O(m times n)，其中 m 和 n 分别是矩阵的行数和列数。我们最多只需要遍历整个矩阵两到三次。
• 空间复杂度：O(1)，仅使用了几个布尔变量，达到了常量级别的额外空间要求。

💡 避坑指南
在处理顺序上，一定要先处理内部矩阵，最后再处理首行首列。如果提前把首行首列置零了，后续遍历内部矩阵时就会因为读到首行首列的 0 而产生错误的覆盖（导致整个矩阵都被置零）。

这种“复用边界作为标记”的思路在矩阵题里很经典。接下来要不要看看类似套路的 LeetCode 48. 旋转图像，它也是原地操作的经典？