【力扣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.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

进阶：

• 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案
• 你能想出一个仅使用常量空间的解决方案吗

二、解题思路总览

核心问题：如何记录哪些行和列需要置零，同时不破坏原矩阵？

解决方案：两次遍历 + 额外数组记录

三、完整代码

classSolution{public:voidsetZeroes(vector<vector<int>>&matrix){intm=matrix.size();intn=matrix[0].size();vector<int>row(m,0);// 记录哪些行需要置零vector<int>col(n,0);// 记录哪些列需要置零// 第一次遍历：扫描矩阵，记录需要置零的行和列for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(matrix[i][j]==0){row[i]=1;col[j]=1;}}}// 第二次遍历：根据记录，将对应行和列置零for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(row[i]||col[j]){matrix[i][j]=0;}}}}};

四、算法流程图

4.1 整体流程

输入：matrix（m x n 矩阵） [Step 1] 获取矩阵尺寸 m = matrix.size() n = matrix[0].size() | v [Step 2] 创建辅助数组 row = vector<int>(m, 0) col = vector<int>(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] 第一次遍历（标记）： i=0, j=0: matrix[0][0]=1 != 0 → 跳过 i=0, j=1: matrix[0][1]=1 != 0 → 跳过 i=0, j=2: matrix[0][2]=1 != 0 → 跳过 i=1, j=0: matrix[1][0]=1 != 0 → 跳过 i=1, j=1: matrix[1][1]=0 == 0 → row[1]=1, col[1]=1 i=1, j=2: matrix[1][2]=1 != 0 → 跳过 i=2, j=0: matrix[2][0]=1 != 0 → 跳过 i=2, j=1: matrix[2][1]=1 != 0 → 跳过 i=2, j=2: matrix[2][2]=1 != 0 → 跳过 标记结果： row = [0, 1, 0] col = [0, 1, 0] 第二次遍历（置零）： i=0, j=0: row[0]=0 且 col[0]=0 → 保持 1 i=0, j=1: row[0]=0 但 col[1]=1 → 置零 i=0, j=2: row[0]=0 且 col[2]=0 → 保持 1 i=1, j=0: row[1]=1 → 置零 i=1, j=1: row[1]=1 且 col[1]=1 → 置零 i=1, j=2: row[1]=1 → 置零 i=2, j=0: row[2]=0 且 col[0]=0 → 保持 1 i=2, j=1: row[2]=0 但 col[1]=1 → 置零 i=2, j=2: row[2]=0 且 col[2]=0 → 保持 1 输出矩阵： [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

五、逐行解析

5.1 创建辅助数组

vector<int>row(m,0);// 记录哪些行需要置零，初始化全为 0vector<int>col(n,0);// 记录哪些列需要置零，初始化全为 0

原理：用两个一维数组分别记录需要置零的行和列。数组下标对应行号或列号，值为 1 表示需要置零。

空间复杂度：O(m + n)

5.2 第一次遍历：标记

for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(matrix[i][j]==0){row[i]=1;col[j]=1;}}}

原理：遍历整个矩阵，找到所有值为 0 的元素，将其所在行和列标记。

时间复杂度：O(m * n)

5.3 第二次遍历：置零

for(inti=0;i<m;i++){for(intj=0;j<n;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(vector<vector<int>>&matrix){intm=matrix.size();intn=matrix[0].size();// 判断第一行和第一列是否需要置零boolfirstRowZero=false;boolfirstColZero=false;for(intj=0;j<n;j++){if(matrix[0][j]==0){firstRowZero=true;break;}}for(inti=0;i<m;i++){if(matrix[i][0]==0){firstColZero=true;break;}}// 用第一行和第一列作为标记for(inti=1;i<m;i++){for(intj=1;j<n;j++){if(matrix[i][j]==0){matrix[i][0]=0;// 标记第 i 行matrix[0][j]=0;// 标记第 j 列}}}// 根据标记置零（跳过第一行和第一列）for(inti=1;i<m;i++){for(intj=1;j<n;j++){if(matrix[i][0]==0||matrix[0][j]==0){matrix[i][j]=0;}}}// 处理第一行和第一列if(firstRowZero){for(intj=0;j<n;j++){matrix[0][j]=0;}}if(firstColZero){for(inti=0;i<m;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 i

6.4 三种方案对比

七、复杂度分析

7.1 本题解法

7.2 进阶原地算法

八、面试追问

九、相关题目