73. 矩阵置零
2021年3月21日每日一题
O(1)额外空间写法
简单理解一下
首先我们对于矩阵内所有\(\sum_{i=0}^{m}{\sum_{j=1}^{n}}0\)，记录到第0行和第0列上
那么，我们只需要对于\(\sum_{i=1}^{m}{\sum_{j=1}^{n}}\)，只需要根据第0行和第0列来置0即可
无论第0行和第0列原先是否是0，其对应的列/行，必定变为0
那么，我们考虑第0行对应的行
我们可以发现，它有\(m[0][0]\)来控制，只要是0，那么整行都是0。
我们再考虑第0列对应的列
我们可以发现，遍历每一行会对每一行的第0列进行更改，我们需要在遍历前，记录原先第\(i\)行第0列的是否为0，只要有一个\([i][0]\)是0，那么显然第0列全为0
代码
class Solution {
public:
void setZeroes(vector<vector<int>> &matrix) {
int n, m;
m = matrix.size();
n = matrix[0].size();
bool rs=0;
for (int i = 0; i < m; i++) {
//每一行头部原本是否有0
//包含原本的[0,0]
if(matrix[i][0]==0)
rs=1;
//判断每列里是否有0
//第0行只对[0,0]有影响
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 i=0;i<n;i++)
matrix[0][i]=0;
if(rs)
for(int i=0;i<m;i++)
matrix[i][0]=0;
}
};