给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
思路
想法
第二种方法不高效的地方在于我们会重复对同一行或者一列赋零。我们可以推迟对行和列赋零的操作。
我们可以用每行和每列的第一个元素作为标记，这个标记用来表示这一行或者这一列是否需要赋零。这意味着对于每个节点不需要访问 M+NM+N 个格子而是只需要对标记点的两个格子赋值。
if cell[i][j] == 0 { cell[i][0] = 0 cell[0][j] = 0 } 这些标签用于之后对矩阵的更新，如果某行的第一个元素为零就将整行置零，如果某列的第一个元素为零就将整列置零。
算法
遍历整个矩阵，如果 cell[i][j] == 0 就将第 i 行和第 j 列的第一个元素标记。
第一行和第一列的标记是相同的，都是 cell[0][0]，所以需要一个额外的变量告知第一列是否被标记，同时用 cell[0][0] 继续表示第一行的标记。
然后，从第二行第二列的元素开始遍历，如果第 r 行或者第 c 列被标记了，那么就将 cell[r][c] 设为 0。这里第一行和第一列的作用就相当于方法一中的 row_set 和 column_set 。
然后我们检查是否 cell[0][0] == 0 ，如果是则赋值第一行的元素为零。
然后检查第一列是否被标记，如果是则赋值第一列的元素为零。
作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/ju-zhen-zhi-ling-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int flag = 1;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) flag = 0;
}
for (int i = 0; i < n; i++) {
if (matrix[0][i] == 0) matrix[0][0] = 0;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < n; i++) {
if (matrix[0][i] == 0) for (int j = 0; j < m; j++) matrix[j][i] = 0;
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) for (int j = 0; j < n; j++) matrix[i][j] = 0;
}
if (flag == 0) for (int j = 0; j < m; j++) matrix[j][0] = 0;
}
};
写的很丑，尽力了。
总结
第二种方法不高效的地方在于我们会重复对同一行或者一列赋零。我们可以推迟对行和列赋零的操作。
我们可以用每行和每列的第一个元素作为标记，这个标记用来表示这一行或者这一列是否需要赋零。
推迟修改，进行标记，通过添加额外的信息来解决问题。
京公网安备 11010502036488号