LeetCode 补拙笔记

0. 前言

• 日期：2026.07.13
• 题目：73. 矩阵置零
• 难度：中等
• 标签：矩阵、原地标记、数组

1. 题目理解

问题描述 给定 m × n 整数矩阵，如果某个元素是 0，则将它所在的整行、整列全部置为 0；要求使用常数级额外空间原地修改矩阵。

示例

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]

2. 解题思路

核心观察

1. 常规思路用额外数组标记行列，空间不达标；进阶方案复用第一行、第一列作为标记位，仅用两个布尔变量单独标记首行、首列本身是否含0；
2. 遍历非首行首列元素，若元素为0则把对应行首、列首标记为0；
3. 反向遍历非首行首列，根据标记位置零；最后根据布尔变量处理首行首列。
4. 优化方向：合并重复遍历逻辑，减少多层嵌套if分支，简化首行首列判断。

算法步骤

原版思路：

1. 单独遍历首行、首列，用布尔变量记录是否存在0；
2. 遍历剩余单元格，用首行首列做标记；
3. 根据行标记逐行置零、根据列标记逐列置零；
4. 依据布尔变量补全首行、首列置零。

优化思路：

1. 一次遍历同时完成首行首列标记与内部单元格标记；
2. 倒序遍历矩阵内部，统一根据标记赋值，减少嵌套if；
3. 统一处理首行首列填充逻辑，消除冗余条件判断。

3. 代码实现

package lc0_lc99.lc73;

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

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

        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;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 0; j < n; j++) matrix[i][j] = 0;
            }
        }

        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 0; i < m; i++) matrix[i][j] = 0;
            }
        }

        if (row0) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (col0) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
}

4. 代码优化说明

class Solution {
public void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;
    // 单次遍历同步标记首行、首列与内部单元格，合并两层循环
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                if (i == 0) firstRowZero = true;
                if (j == 0) firstColZero = true;
                if (i != 0 && j != 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
    }
    // 倒序填充内部单元格，避免标记被提前覆盖，单层循环无嵌套if
    for (int i = m - 1; i >= 1; i--) {
        for (int j = n - 1; j >= 1; j--) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    // 批量填充首行
    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;
    }
}
}

5. 复杂度分析

• 原始版本 时间复杂度：$O(mn)$，多轮嵌套循环遍历矩阵，多层if分支判断 空间复杂度：$O(1)$，仅两个布尔标记变量，原地修改矩阵
• 优化版本 时间复杂度：$O(mn)$，总遍历次数减少，合并独立的首行、首列预扫描循环，精简嵌套条件分支 空间复杂度：$O(1)$，无额外数组，仅常数临时变量

6. 总结

• 核心：复用矩阵首行首列作为零标记，仅两个布尔变量记录首行首列原始零状态，满足常数空间要求；
• 优化亮点：合并三次独立预扫描为单次双层遍历，消除重复循环；倒序填充内部单元格，统一行/列标记判断逻辑，减少多层嵌套if；
• 关键陷阱：必须先完成全部标记再置零，若提前修改首行首列会破坏标记信息。