题目描述
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example1:
Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ]
Example2:
Input: [ [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] ]
Note:
- 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?
解题思路
- 这道题中说的空间复杂度为O(mn)的解法自不用多说，直接新建一个和matrix等大小的矩阵，
- 然后一行一行的扫，只要有0，就将新建的矩阵的对应行全赋0，行扫完再扫列，然后把更新完的矩阵赋给matrix即可
- O(m + n) // 我们可以新建一个row，col负责存储哪些行，那些列都有0元素
- 最后遍历这些行，列，进行赋值即可
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
vector<int> row;
vector<int> col;
for(int i = 0; i < matrix.size(); i++){
for(int j = 0; j < matrix[0].size(); j++){
if(matrix[i][j] == 0){
row.push_back(i);
col.push_back(j);
}
}
}
int i = 0;
while(i < row.size()){
for(int j = 0; j < matrix[0].size(); j++){
matrix[row[i]][j] = 0;
}
i++;
}
i = 0;
while(i < col.size()){
for(int j = 0; j < matrix.size(); j++){
matrix[j][col[i]] = 0;
}
i++;
}
}
};
