【力扣100题】22. 矩阵置零

一、题目描述给定一个 m x n 的矩阵如果一个元素为 0则将其所在行和列的所有元素都设为 0。请使用原地算法。示例 1输入matrix [[1,1,1],[1,0,1],[1,1,1]] 输出[[1,0,1],[0,0,0],[1,0,1]]示例 2输入matrix [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出[[0,0,0,0],[0,4,5,0],[0,3,1,0]]提示m matrix.lengthn matrix[0].length1 m, n 200-2^31 matrix[i][j] 2^31 - 1进阶一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案你能想出一个仅使用常量空间的解决方案吗二、解题思路总览核心问题如何记录哪些行和列需要置零同时不破坏原矩阵解决方案两次遍历 额外数组记录遍历操作第一次遍历扫描整个矩阵遇到 0 就记录该行该列需要置零第二次遍历根据记录将对应行和列的所有元素置零方案时间复杂度空间复杂度暴力解每个0都遍历行列O(mn * (mn))O(1)额外数组记录本题O(mn)O(mn)原地算法进阶O(mn)O(1)三、完整代码classSolution{public:voidsetZeroes(vectorvectorintmatrix){intmmatrix.size();intnmatrix[0].size();vectorintrow(m,0);// 记录哪些行需要置零vectorintcol(n,0);// 记录哪些列需要置零// 第一次遍历扫描矩阵记录需要置零的行和列for(inti0;im;i){for(intj0;jn;j){if(matrix[i][j]0){row[i]1;col[j]1;}}}// 第二次遍历根据记录将对应行和列置零for(inti0;im;i){for(intj0;jn;j){if(row[i]||col[j]){matrix[i][j]0;}}}}};四、算法流程图4.1 整体流程输入matrixm x n 矩阵 [Step 1] 获取矩阵尺寸 m matrix.size() n matrix[0].size() | v [Step 2] 创建辅助数组 row vectorint(m, 0) col vectorint(n, 0) | v [Step 3] 第一次遍历扫描并标记 | v for i 0 to m-1: for j 0 to n-1: matrix[i][j] 0 ? |是 |否 v v row[i] 1 继续 col[j] 1 | | v ---- 继续内层循环 -- | v 内层循环结束 | v 回到外层循环或下一步 | v [Step 4] 第二次遍历置零 | v for i 0 to m-1: for j 0 to n-1: row[i] || col[j] ? |是 |否 v v matrix[i][j] 0 继续不变 | | v v 【返回】 【返回】4.2 第一次遍历标记详细流程外层循环i 0 to m-1 内层循环j 0 to n-1 | v matrix[i][j] 0 ? |否 v 继续 j |是 v row[i] 1 col[j] 1 | v 继续 j 内层循环 j 结束后 | v i 继续外层循环 所有遍历完成后 row 数组标记了所有含 0 的行 col 数组标记了所有含 0 的列4.3 第二次遍历置零详细流程外层循环i 0 to m-1 内层循环j 0 to n-1 | v row[i] 1 或 col[j] 1 |是 v matrix[i][j] 0 | v 继续 j |否该位置不变 | v 继续 j 内层循环 j 结束后 | v i 继续外层循环4.4 具体示例执行流程输入矩阵 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] m 3, n 3 row [0, 0, 0] col [0, 0, 0] 第一次遍历标记 i0, j0: matrix[0][0]1 ! 0 → 跳过 i0, j1: matrix[0][1]1 ! 0 → 跳过 i0, j2: matrix[0][2]1 ! 0 → 跳过 i1, j0: matrix[1][0]1 ! 0 → 跳过 i1, j1: matrix[1][1]0 0 → row[1]1, col[1]1 i1, j2: matrix[1][2]1 ! 0 → 跳过 i2, j0: matrix[2][0]1 ! 0 → 跳过 i2, j1: matrix[2][1]1 ! 0 → 跳过 i2, j2: matrix[2][2]1 ! 0 → 跳过 标记结果 row [0, 1, 0] col [0, 1, 0] 第二次遍历置零 i0, j0: row[0]0 且 col[0]0 → 保持 1 i0, j1: row[0]0 但 col[1]1 → 置零 i0, j2: row[0]0 且 col[2]0 → 保持 1 i1, j0: row[1]1 → 置零 i1, j1: row[1]1 且 col[1]1 → 置零 i1, j2: row[1]1 → 置零 i2, j0: row[2]0 且 col[0]0 → 保持 1 i2, j1: row[2]0 但 col[1]1 → 置零 i2, j2: row[2]0 且 col[2]0 → 保持 1 输出矩阵 [[1, 0, 1], [0, 0, 0], [1, 0, 1]]五、逐行解析5.1 创建辅助数组vectorintrow(m,0);// 记录哪些行需要置零初始化全为 0vectorintcol(n,0);// 记录哪些列需要置零初始化全为 0原理用两个一维数组分别记录需要置零的行和列。数组下标对应行号或列号值为 1 表示需要置零。空间复杂度O(m n)5.2 第一次遍历标记for(inti0;im;i){for(intj0;jn;j){if(matrix[i][j]0){row[i]1;col[j]1;}}}原理遍历整个矩阵找到所有值为 0 的元素将其所在行和列标记。时间复杂度O(m * n)5.3 第二次遍历置零for(inti0;im;i){for(intj0;jn;j){if(row[i]||col[j]){matrix[i][j]0;}}}原理再次遍历矩阵如果当前元素所在行或列被标记过row[i] || col[j] 为真则将该元素置零。逻辑只要行被标记 OR 列被标记该元素就需要置零。六、进阶原地算法 O(1) 空间6.1 核心思想用矩阵的第一行和第一列作为标记数组代替 row 和 col 的作用。问题如何区分「原本就是 0」和「被置零后变成 0」解决方案在遍历前先判断第一行和第一列是否需要置零然后用它们作为标记。6.2 进阶代码classSolution{public:voidsetZeroes(vectorvectorintmatrix){intmmatrix.size();intnmatrix[0].size();// 判断第一行和第一列是否需要置零boolfirstRowZerofalse;boolfirstColZerofalse;for(intj0;jn;j){if(matrix[0][j]0){firstRowZerotrue;break;}}for(inti0;im;i){if(matrix[i][0]0){firstColZerotrue;break;}}// 用第一行和第一列作为标记for(inti1;im;i){for(intj1;jn;j){if(matrix[i][j]0){matrix[i][0]0;// 标记第 i 行matrix[0][j]0;// 标记第 j 列}}}// 根据标记置零跳过第一行和第一列for(inti1;im;i){for(intj1;jn;j){if(matrix[i][0]0||matrix[0][j]0){matrix[i][j]0;}}}// 处理第一行和第一列if(firstRowZero){for(intj0;jn;j){matrix[0][j]0;}}if(firstColZero){for(inti0;im;i){matrix[i][0]0;}}}};6.3 进阶流程图[Step 1] 判断第一行是否含 0 firstRowZero matrix[0][j] 0 | v [Step 2] 判断第一列是否含 0 firstColZero matrix[i][0] 0 | v [Step 3] 用第一行和第一列作为标记数组 for i 1 to m-1: for j 1 to n-1: matrix[i][j] 0 |是 v matrix[i][0] 0 // 标记行 matrix[0][j] 0 // 标记列 | v [Step 4] 根据标记置零排除第一行第一列 for i 1 to m-1: for j 1 to n-1: matrix[i][0] 0 或 matrix[0][j] 0 |是 v matrix[i][j] 0 | v [Step 5] 处理第一行 firstRowZero |是 v matrix[0][j] 0 for all j | v [Step 6] 处理第一列 firstColZero |是 v matrix[i][0] 0 for all i6.4 三种方案对比方案时间复杂度空间复杂度特点暴力解O(mn * (mn))O(1)每个0都遍历行列时间太慢额外数组本题O(mn)O(mn)两遍遍历空间稍大原地算法进阶O(mn)O(1)用第一行/列作为标记最优七、复杂度分析7.1 本题解法指标复杂度说明时间复杂度O(m * n)两次遍历矩阵空间复杂度O(m n)row 数组 m 个col 数组 n 个7.2 进阶原地算法指标复杂度说明时间复杂度O(m * n)三次遍历矩阵空间复杂度O(1)只用几个布尔变量八、面试追问问题回答要点为什么需要两次遍历第一次标记记录哪些行/列要置零第二次执行置零。如果边标记边置零会导致后续判断出错row[i]空间复杂度能进一步优化吗可以用矩阵第一行和第一列作为标记数组实现 O(1) 空间原地算法中 firstRowZero 的作用记录第一行本身是否需要置零因为第一行会被用作标记不能直接置零为什么原地算法要跳过第一行第一列第一行和第一列被用作标记数组如果对它们执行置零操作会丢失标记信息原地算法如何恢复第一行第一列最后根据 firstRowZero 和 firstColZero 单独处理第一行和第一列这个题有没有其他解法还有一种方案是设置一个 sentinel 值如 INFINITY来标记但会改变矩阵范围外的状态不推荐九、相关题目题号题目关键点73矩阵置零本题48旋转图像矩阵旋转54螺旋矩阵矩阵遍历59螺旋矩阵 II矩阵生成289生命游戏原地算法用位操作标记