如果某个元素是0，那么将它所在的一行和一列都改为0.
思路：注意，如果在原地直接修改， 不能影响后面的判断。
方法有三种：
方法1：使用辅助空间记录需要改为0的行和列,空间复杂度O(m+n), 时间复杂度O(m*n)
void setZeroes(vector<vector<int>>& matrix) { std::set<int> zero_rows; std::set<int> zero_cols; for (int i = 0; i < matrix.size(); ++i) { for (int j = 0; j < matrix[0].size(); ++j) { if (matrix[i][j] == 0) { zero_rows.insert(i); zero_cols.insert(j); } } } for (int i = 0; i < matrix.size(); ++i) { for (int j = 0; j < matrix[0].size(); ++j) { if (zero_rows.count(i) > 0 || zero_cols.count(j) > 0) { matrix[i][j] = 0; } } } }方法2：直接在原地标记，为了不影响后面判断，将1改为非0和1 的值。在第二次遍历时再将所有标记需要改为0的值改为0.
空间复杂度O(1), 时间复杂度O(m*n)*(m+n), 这里需要注意的是 只将需要改为0的1 改为MODIFY，0不能改。
void setZeroes(vector<vector<int>>& matrix) { int MODIFIED = -1000000; int rows = matrix.size(); int cols = matrix[0].size(); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (matrix[i][j] == 0) { for (int k = 0; k < rows; ++k) { if (matrix[k][j] != 0) { matrix[k][j] = MODIFIED; } } for (int k = 0; k < cols; ++k) { if (matrix[i][k] != 0) { matrix[i][k] = MODIFIED; } } } } } for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (matrix[i][j] == MODIFIED) { matrix[i][j] = 0; } } } }方法3：利用第一行和第一列标记需要改为0的行和列，这种方法在编写代码时，需要考虑比较多，容易出bug，时间空间复杂度基本同方法2，根据这几点的考虑，个人认为尽量使用第二种方法比较好。
void setZeroes(vector<vector<int>>& matrix) { if (matrix.size() == 0) { return ; } int rows = matrix.size(); int cols = matrix[0].size(); bool first_row_has_zero = false; bool first_col_has_zero = false; for (int i = 0; i < cols; ++i) { if (matrix[0][i] == 0) { first_row_has_zero = true; } } for (int i = 0; i < rows; ++i) { if (matrix[i][0] == 0) { first_col_has_zero = true; } } // 如果某个元素是0，那么就把它对应的首行和首列对应位置置为0，为了方便之后把整行和整列置为0. for (int i = 1; i < rows; ++i) { for (int j = 1; j < cols; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // 行置0 for (int i = 1; i < rows; ++i) { if (matrix[i][0] == 0) { for (int j = 1; j < cols; ++j) { matrix[i][j] = 0; } } } // 列置0 for(int j = 1; j < cols; ++j) { if (matrix[0][j] == 0) { for (int i = 1; i < rows; ++i) { matrix[i][j] = 0; } } } // 首行 if (first_row_has_zero) { for (int j = 0; j < cols; ++j) { matrix[0][j] = 0; } } // 首列 if (first_col_has_zero) { for (int j = 0; j < rows; ++j) { matrix[j][0] = 0; } } }
