题目描述
Given an
m x n
matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
例子
例子 1
Input:
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output:[[1,0,1],[0,0,0],[1,0,1]]
例子 2
Input:
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Follow Up
- A straight forward solution using
O(mn)
space is probably a bad idea.- A simple improvement uses
O(m + n)
space, but still not the best solution.- Could you devise a constant space solution?
解题思路
题目要求很简单,遍历一个数组,遇到 0 的元素则将对应行和列的元素都设为 0。思路如下:
- 首先肯定不能边做边改,因为这样会影响后续元素的判断(原本不是 0 的元素被设为 0)
- 那么很直观可以想到一个
O(mn)
的方法,创建一个等大小的标志位数组,用来存储对应元素是否为 0,然后再根据标志位数据设置相对行和列的元素为 0 即可 - 上述的方法有很大程度的数据是浪费的,因为对于一个行和列只需要由一个元素为 0 那么该行和该列都要设置为 0,所以我们只需要用
O(m + n)
的空间来存储哪些行和列有元素为 0 即可 - 题目进一步要求有没有办法将所需空间降为常数级别的,我们可以想到用每一行和每一列的首元素作为标志位,注意这里必须是首元素,因为要保证标志位不受后续遍历的影响(假如用末元素作为标志位,那么我们先对标志位做出修改然后再判断,则可能会出现误判)。这种方法相当于将上一种方法用到的
O(m + n)
空间用数组中的第一行和第一列来代替了,但是这样的话可以想见第一行和和第一列的判断则会出现影响,这个问题很好解决,只需要用两个变量分别作为第一行和第一列的标志位即可(因此空间复杂度为矩阵的维度,这里是 2)
代码如下:
#include <vector>
class Solution {
public:
void setZeroes(std::vector<std::vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool first_row = false;
bool first_col = false;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
if (i == 0) {
first_row = true;
}
if (j == 0) {
first_col = true;
}
}
}
}
for (int i = 1; i < m; ++i) {
if (matrix[i][0] == 0) {
for (int j = 1; j < n; ++j) {
matrix[i][j] = 0;
}
}
}
for (int i = 1; i < n; ++i) {
if (matrix[0][i] == 0) {
for (int j = 1; j < m; ++j) {
matrix[j][i] = 0;
}
}
}
if (first_row) {
for (int i = 0; i < n; ++i) {
matrix[0][i] = 0;
}
}
if (first_col) {
for (int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
}
};
- 时间复杂度:
O(mn)
- 空间复杂度:
O(dim(matrix)) -> O(1)
GitHub 代码同步地址: 73.SetMatrixZeroes.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions