hot100 矩阵置零(73)

本题采用标记数组的解法来解决“矩阵置零”问题。其核心本质是将“零元素的冲突探测”与“矩阵的实际改写”进行解耦利用空间换时间的策略引入两个独立的布尔型数组分别记录需要清零的行与列。当前解法成功将空间复杂度由暴力克隆矩阵的 O(m x n) 优化至 O(m n)最终走向是通过两次完备的二维拓扑遍历精确实现矩阵的原地清零。一、 问题本质与数据模型对于一个大小为 m x n 的二维矩阵 matrix若某个单元格matrix[i][j] 0则需要将其所在的整行第 i 行和整列第 j 列的所有元素全部重置为 0。该问题存在一个核心的物理陷阱如果在遍历矩阵的过程中一旦发现 0 就立即对其所在的行和列进行清零改写那么这些新生成的 0 会在后续的遍历中被错误地识别为“原始输入的 0”从而引发灾难性的“全零扩散”导致整个矩阵最终全部变成 0。为了打破这种状态交织的恶性循环必须将“探测阶段”与“修改阶段”彻底分离探测阶段只记录哪些行、哪些列应该被清零绝不破坏原始矩阵的数据流。修改阶段根据探测阶段留下的“账本”集中对矩阵进行统一的改写。当前解法引入了两个一维布尔数组作为标记账本row[m]长度为 mrow[i] true代表第 i 行至少包含一个原始的 0整行需要被清零。col[n]长度为 ncol[j] true代表第 j 列至少包含一个原始的 0整列需要被清零。二、 算法演进对比在解决二维矩阵的行列联动修改问题时不同空间策略的选择决定了算法的演进路径解法名称时间复杂度空间复杂度核心原理物理缺陷 / 瓶颈矩阵暴力克隆O(m x n)O(m x n)复制一份完全相同的备份矩阵遍历备份矩阵在原矩阵上进行行列清零制造了与原矩阵完全等量的数据冗余内存开销过大外部标记数组当前解法O(m x n)O(m n)抽取行、列两个维度的一维数组进行独立状态标记解耦探测与改写需要申请额外的线性空间在超大规模矩阵下仍有优化空间内部首行首列复用O(m x n)O(1)将矩阵的第一行和第一列虚拟化为标记数组利用额外两个变量记录首行首列自身的安全状态逻辑判断分支极其复杂极易发生状态覆盖与边界丢失三、 核心控制逻辑拆解提供的源码执行流程非常清晰分为两个独立的双重循环1. 状态收集阶段第一轮双重循环遍历整个 m x n 矩阵中的每一个元素。判定条件if (matrix[i][j] 0)。状态打标一旦命中立刻执行row[i] true和col[j] true。逻辑事实此阶段没有发生任何的矩阵赋值操作矩阵的原始拓扑结构完好损。2. 状态落地阶段第二轮双重循环再次全面遍历该 m x n 矩阵。复合判定条件if (row[i] || col[j])。数学含义对于任意坐标(i, j)只要它所处的行i在标记账本中为真或者它所处的列j在标记账本中为真就说明它处于清零的交叉火力网上。最终赋值执行matrix[i][j] 0完成原地的行列抹杀。四、 算法执行状态机步进示例以输入数据matrix [[1,1,1], [1,0,1], [1,1,1]]为例矩阵规模为 3 x 3。算法内部变量的演进状态如下表所示阶段 / 步骤正在处理的坐标单元格数值账本 row 状态变化账本 col 状态变化矩阵内部元素实时状态初始化--[false, false, false][false, false, false][[1,1,1], [1,0,1], [1,1,1]]探测 (0,0)到(1,0)(0,0) 到 (1,0)全为 1无变化无变化无变化探测 (1,1)(1,1)0更新row[1] true[false, true, false]更新col[1] true[false, true, false]矩阵内部无变化保护现场探测 剩余位置(1,2) 到 (2,2)全为 1探测结束最终账本row [false, true, false]探测结束最终账本col [false, true, false]探测期完美结束改写第 0 行(0,0) 到 (0,2)-row[0]false, 只有col[1]true触发col[1]触发位置 (0,1)矩阵变为[[1,0,1], [1,0,1], [1,1,1]]改写第 1 行(1,0) 到 (1,2)-row[1]true触发整行清零无论 col 为何全行重置为 0矩阵变为[[1,0,1], [0,0,0], [1,1,1]]改写第 2 行(2,0) 到 (2,2)-row[2]false, 只有col[1]true触发col[1]触发位置 (2,1)矩阵最终确定[[1,0,1], [0,0,0], [1,0,1]]五、源码实现class Solution { public void setZeroes(int[][] matrix) { // 获取矩阵的行数 m 和列数 n int m matrix.length; int n matrix[0].length; // 声明行标记数组和列标记数组用于存储需要清零的轨迹 boolean[] row new boolean[m]; boolean[] col new boolean[n]; // 步骤 1第一轮双重循环负责扫描矩阵并记录 0 的位置 for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 0) { // 记录第 i 行和第 j 列需要被重置 row[i] true; col[j] true; } } } // 步骤 2第二轮双重循环根据标记数组的记录原地改写矩阵 for (int i 0; i m; i) { for (int j 0; j n; j) { // 短路逻辑当前行或者当前列被标记为 true 时当前位置的元素直接置为 0 if (row[i] || col[j]) { matrix[i][j] 0; } } } } }六、 复杂度分析1. 时间复杂度O(m x n)分析算法包含两个平行的、互不嵌套的双重循环。第一个双重循环遍历整个 m x n 矩阵进行 0 元素的探测执行步数为 m x n。第二个双重循环同样完整遍历一次 m x n 矩阵进行元素清零改写执行步数为 m x n。结论总的基本指令执行次数为 2 x m x n。抛弃常数项后整体时间复杂度与矩阵的总元素个数呈严格的线性正比关系即 O(m x n)。2. 空间复杂度O(m n)分析算法在运行期间独立申请了两个一维的布尔型辅助数组。行标记数组row的空间消耗与矩阵的行数 m 呈线性相关占用 m 个 boolean 空间。列标记数组col的空间消耗与矩阵的列数 n 呈线性相关占用 n 个 boolean 空间。结论除了这两个数组外仅使用了常数个整型控制变量m,n,i,j。因此算法的额外辅助空间复杂度为 O(m n)。