73. 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

✅ 解题思路：

这道题的难点是：不能新建一个同样大小的矩阵来标记，否则空间复杂度是 O(m × n)。
为了达到 原地修改 和 O(1) 空间复杂度，我们用 第一行和第一列作为标记空间。

🔍 代码

class Solution {
    public void setZeroes(int[][] matrix) {
        int rowCount = matrix.length; // number of rows in the matrix // 行数
        int colCount = matrix[0].length; // number of columns in the matrix // 列数

        boolean firstRowHasZero = false; // flag to check if the first row contains a zero // 第一行是否包含 0
        boolean firstColHasZero = false; // flag to check if the first column contains a zero // 第一列是否包含 0

        // Check if the first row has any zeros // 检查第一行是否有0
        for (int col = 0; col < colCount; ++col) {
            if (matrix[0][col] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // Check if the first column has any zeros // 检查第一列是否有0
        for (int row = 0; row < rowCount; ++row) {
            if (matrix[row][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }

        // Use the first row and column as markers.
        // Set matrix[i][0] and matrix[0][j] to 0 if matrix[i][j] is 0
        // 使用第一行和第一列作为标记，如果 matrix[i][j] 为 0，就将 matrix[i][0] 和 matrix[0][j] 设为 0
        for (int row = 1; row < rowCount; ++row) {
            for (int col = 1; col < colCount; ++col) {
                if (matrix[row][col] == 0) {
                    matrix[row][0] = 0;
                    matrix[0][col] = 0;
                }
            }
        }

        // Iterate over the matrix again using the first row and column as reference,
        // and set the elements to 0 accordingly.
        // 再次遍历矩阵，用第一行和第一列做参考，根据标记把对应位置设为 0
        for (int row = 1; row < rowCount; ++row) {
            for (int col = 1; col < colCount; ++col) {
                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
                    matrix[row][col] = 0;
                }
            }
        }

        // Nullify the first row if needed // 如果第一行原本有0，就把整行都设为0
        if (firstRowHasZero) {
            for (int col = 0; col < colCount; ++col) {
                matrix[0][col] = 0;
            }
        }

        // Nullify the first column if needed // 如果第一列原本有0，就把整列都设为0
        if (firstColHasZero) {
            for (int row = 0; row < rowCount; ++row) {
                matrix[row][0] = 0;
            }
        }
    }
}

✨ 总结重点：

这样做的优点是：不使用额外的空间，只在原数组上操作，时间复杂度为 O(m × n)，空间复杂度为 O(1)。

🧩 为啥不能直接改？

因为如果你一边遍历一边改，比如刚遇到一个 0，你把那一行一列都变成 0，那么你下一次就可能误以为其他原本不是 0 的地方也要变成 0，逻辑就错了。

✅ 所以我们做了啥？

我们利用第一行和第一列当成“记事本”（占位标记）来“记下”哪一行和哪一列最终需要变成 0。

比如，如果我们发现 matrix[2][3] 是 0，我们就做：

matrix[2][0] = 0; // 表示第2行要变成0

matrix[0][3] = 0; // 表示第3列要变成0

🔍 关键代码部分是：

for (int row = 1; row < rowCount; ++row) {

for (int col = 1; col < colCount; ++col) {

// 如果这一行在第一列被标记为0，或者这一列在第一行被标记为0

if (matrix[row][0] == 0 || matrix[0][col] == 0) {

matrix[row][col] = 0; // 就把这个元素设成0 }

} }

✅ 总结：

第一行第一列作为“标记区”是为了记住哪一行/列最终需要清零。
在后续再次遍历时，我们通过看：

matrix[row][0] == 0 // 这一行要变0 matrix[0][col] == 0 // 这一列要变0

来决定当前元素是否要变为 0。