Leetcode-Set Matrix Zeroes

题目描述

Set Matrix Zeroes

1
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

分析

这是咋看起来很简单,就是把0的横竖都置成0,但是其核心是在线处理!

不能使用多余的空间。

一开始的思路,还是一个标记,就是对存在0的横行和竖列都进行标记,最后还能恢复成0.

一开始想用最大整数/最小整数进行标记,但是测试用例中,就存在这样的用例!

所以,一直不能AC。

后来,看了discuss,是对第一行和第一列进行标记实现的。而对于第一列的情况,还需要单独处理一下。

值得注意的是,最后进行恢复为0的时候,需要从最后一排,最后一列开始,倒过来恢复。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int col0 = 1;
for(int i=0;i<m;i++){
if(matrix[i][0] == 0)
col0 = 0;
for(int j=1;j<n;j++){
if(matrix[i][j]==0){
matrix[0][j] = matrix[i][0] = 0;
}
}
}

for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=1;j--){
if(matrix[i][0]==0 || matrix[0][j]==0)
matrix[i][j] = 0;
}
if(col0==0)
matrix[i][0] = 0;
}

}
};