目录
题目描述
给定一个 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) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？
题解
方法一：直观法：使用额外的布尔矩阵来标记
遍历原始矩阵 matrix，找到所有为 0 的元素；
在布尔矩阵 mark 中将它所在行列都标记为 true；
再次遍历原矩阵，如果它所在的行或列在 mark 中有 true，就将它置为 0。
C++ 代码实现
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
// 创建一个标记矩阵
vector<vector<bool>> mark(m, vector<bool>(n, false));
// Step 1: 遍历原矩阵，标记需要置零的行列
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
// 当前这一行、这一列都需要标记
for (int k = 0; k < n; k++) {
mark[i][k] = true;
}
for (int k = 0; k < m; k++) {
mark[k][j] = true;
}
}
}
}
// Step 2: 根据标记置 0
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mark[i][j]) {
matrix[i][j] = 0;
}
}
}
}
};
复杂度分析
- 时间复杂度：O(m × n × (m + n)) ≈ O(m² + n²) 因为每遇到一个 0，就标记一整行一整列（有优化空间）
- 空间复杂度：O(m × n) 使用了一个同样大小的布尔矩阵 mark
方法二：使用标记数组
我们可以创建一个大小为 m 的标记数组 row 和 n 个标记数组 col，用于标记哪些行和列需要置零。 把 matrix[i][j] 置零时，将对应的 row[i] 和 col[j] 标记为 true。 在遍历矩阵时，如果 row[i] 或 col[j] 为 true，则将 matrix[i][j] 置零。
C++ 代码实现
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<bool> row(m, false);
vector<bool> col(n, false);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
};
复杂度分析
- 时间复杂度：O(m * n)，其中 m 和 n 分别为矩阵的行数和列数。
- 空间复杂度：O(m + n)，其中 m 和 n 分别为矩阵的行数和列数。
方法三：使用两个标记变量
我们要用 第一行 和 第一列 代替额外的空间来记录每一行和列是否应该设为 0。
但直接这样做有个问题：我们无法判断原来的第一行和第一列是否本身有 0，因为它们被重用了。
所以我们要 额外使用两个变量，分别记录第一行和第一列是否应该为 0：
row0Flag：第一行是否需要设置为 0
col0Flag：第一列是否需要设置为 0
详细步骤
Step 1：确定第一行和第一列是否需要置零（用两个变量标记）
bool row0Flag = false, col0Flag = false;
// 检查第一列
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) col0Flag = true;
}
// 检查第一行
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) row0Flag = true;
}
Step 2：从 (1,1) 开始遍历，使用第一行和第一列作为标记
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; // 标记这一列
}
}
}
Step 3：根据标记将剩余矩阵元素置零（除了第一行第一列）
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;
}
}
}
Step 4：根据两个标记变量处理第一行和第一列
if (col0Flag) {
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
if (row0Flag) {
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
C++ 代码实现
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool row0Flag = false, col0Flag = false;
// Step 1: 检查第一列是否需要置零
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
col0Flag = true;
}
}
// Step 1: 检查第一行是否需要置零
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
row0Flag = true;
}
}
// Step 2: 用第一行和第一列做标记
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;
}
}
}
// Step 3: 根据标记置零
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;
}
}
}
// Step 4: 处理第一列
if (col0Flag) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
// Step 4: 处理第一行
if (row0Flag) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}
};
复杂度分析
时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
空间复杂度：O(1)，我们只需要常数空间存储若干变量。