73. 矩阵置零

✨核心逻辑

本题要求原地将矩阵中出现 0 的元素所在的行和列全部置为 0。这里采用 “原地标记法（利用首行首列作为标记数组）” 的策略：

前置标记：由于我们要用第一行和第一列作为标记数组，所以必须先遍历并记录第一行和第一列原本是否包含 0，防止后续遍历时的标记操作污染了原信息。
内部标记：从 (1, 1) 开始遍历矩阵内部的所有元素。如果发现某个元素为 0，就将其对应的第一行元素 matrix[0][j] 和第一列元素 matrix[i][0] 标记为 0。
内部置零：再次从 (1, 1) 开始遍历内部元素。检查当前元素对应的首行或首列标记是否为 0。如果是，则直接将当前元素自身置为 0。
外围置零：最后处理首行和首列。根据第一步记录下来的标记，如果首行原本有 0，则将第一行全部置零；如果首列原本有 0，则将第一列全部置零。

🔥代码实现（含详细变量注释）

class Solution {
    public void setZeroes(int[][] matrix) {
        // m：记录矩阵的行数
        int m = matrix.length;
        // n：记录矩阵的列数
        int n = matrix[0].length;
        
        // 第一步：检查第一行和第一列本身是否包含 0（提前备份状态）
        // firstRowHasZero：标记第一行原本是否有 0
        boolean firstRowHasZero = false;
        // firstColHasZero：标记第一列原本是否有 0
        boolean firstColHasZero = false;

        // 遍历第一列，检查是否存在 0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }
        // 遍历第一行，检查是否存在 0
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                firstRowHasZero = true;
                break;
            }
        }
        
        // 第二步：遍历内部矩阵（从 (1,1) 开始），在首行和首列打上标记
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    // 如果内部元素为 0，将其对应的第一行和第一列的元素置为 0 作为标记
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        // 第三步：再次遍历内部矩阵，根据首行和首列的标记，将内部符合条件的元素置 0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 如果当前元素的同列第一行标记为 0，或同行第一列标记为 0，则当前元素置 0
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // 第四步：收尾处理首列和首行自身
        // 如果第一列原本有 0，则把整列全部置为 0
        if (firstColHasZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        // 如果第一行原本有 0，则把整行全部置为 0
        if (firstRowHasZero) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
    }
}

⏱️复杂度分析
- 时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要遍历矩阵进行标记（1次），然后根据标记再次遍历（1次），最后处理首行首列，总操作次数正比于矩阵元素总数。
- 空间复杂度：O(1)，只使用了布尔变量 firstRowHasZero、firstColHasZero 以及循环索引变量 i、j 等常数个额外变量，没有使用额外的数组空间，满足题目对原地算法的要求。