题目描述
给定一个 m x n
的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。
请使用原地算法 。
样例
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶
- 一个直接的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m+n) 的额外空间,但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗?
算法1
(按序遍历) O(mn)
- 我们先按行遍历,遍历每一行时,用数组记录更新每一列中是否出现过 0,然后更新这一行是否全为 0。
- 然后在对每一列进行判断,如果这一列出现过一次 0,则更新这一列。
时间复杂度
- 每个位置遍历常数次,故时间复杂度为 O(mn)。
空间复杂度
- 需要额外的 O(n) 的空间记录每一列是否出现过 0。
C++ 代码
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<bool> zero(n, false);
for (int i = 0; i < m; i++) {
bool z = false;
for (int j = 0; j < n; j++)
if (matrix[i][j] == 0) {
zero[j] = true;
z = true;
}
if (z) {
for (int j = 0; j < n; j++)
matrix[i][j] = 0;
}
}
for (int j = 0; j < n; j++)
if (zero[j]) {
for (int i = 0; i < m; i++)
matrix[i][j] = 0;
}
}
};
算法2
(改进的按序遍历) O(mn)
- 在算法 1 的基础上,想办法不用额外空间记录每一列的 0 的情况。
- 我们决定用第一行的原空间替代算法 1 中
zero
数组的功能。 - 首先用一个布尔变量记录一下原来第一行中是否有 0。
- 然后按照算法 1 的流程,只不过在是在第一行中记录每一列是否有 0,而不是额外的数组中。
- 最后根据之前的布尔变量,决定是否将第一行全部变成 0。
时间复杂度
- 每个位置遍历常数次,故时间复杂度为 O(mn)。
空间复杂度
- 只使用了额外的变量,故空间复杂度为 O(1)。
C++ 代码
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
bool first_row_zero = false;
for (int j = 0; j < n; j++)
if (matrix[0][j] == 0) {
first_row_zero = true;
break;
}
for (int i = 1; i < m; i++) {
bool z = false;
for (int j = 0; j < n; j++)
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
z = true;
}
if (z) {
for (int j = 0; j < n; j++)
matrix[i][j] = 0;
}
}
for (int j = 0; j < n; j++)
if (matrix[0][j] == 0) {
for (int i = 0; i < m; i++)
matrix[i][j] = 0;
}
if (first_row_zero) {
for (int j = 0; j < n; j++)
matrix[0][j] = 0;
}
}
};