力扣每日一题73：矩阵置零

题目描述：

给定一个 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
• -231 <= matrix[i][j] <= 231 - 1

进阶：

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

通过次数

286.9K

提交次数

446.4K

通过率

64.3%

思路和题解：

一、先遍历一次矩阵，用一个数组row和一个数组col标记要置零的行和列，随后再遍历一次矩阵，如果矩阵所在行或列要置0，那就变零。时间复杂度O(m*n)，空间复杂度O(m+n)

代码：

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();//记录要置零的行和列vector<int> row(m,0);vector<int> col(n,0);for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(matrix[i][j]==0)row[i]=col[j]=1;for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(row[i]==1||col[j]==1)matrix[i][j]=0;}
};

二、方法一的改进，矩阵的第一行和第一列代替col和row，实现O(1)空间复杂度，但矩阵的第一行和第一列有交叉，交叉的位置既要标记第一行是否出现零，又要标记第一列是否出现零，所以我们应该额外设置一个变量flag，flag与matrix[0][0]一个标记第一行是否出现零，一个标记第一列是否出现零。

代码：

lass Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();bool flag_col0=false;//标记for(int i=0;i<m;i++){if(matrix[i][0]==0) flag_col0=true;for(int j=1;j<n;j++){if(matrix[i][j]==0)matrix[i][0]=matrix[0][j]=0;}}// 置零for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(matrix[i][0]==0||matrix[0][j]==0)matrix[i][j]=0;}}if(matrix[0][0]==0)for(int j=0;j<n;j++) matrix[0][j]=0;if(flag_col0==true)for(int j=0;j<m;j++) matrix[j][0]=0;}
};