Leetcode73. 矩阵置零（C++思路与代码）_矩阵置零c++

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

思路：
将每一行每一列的第一个元素设置为标识符，如果为0，那么表示这一行或者这一列有元素0。由于第0行和第0列首元素都是[0][0]，所以我们要单独判断第0列设置一个flag。更新矩阵时，从右下角往上更新，因为矩阵的上边和左边为标识符。由于第0列需要单独判断，所以j>=1。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool flag=false;
        int m=matrix.size(),n=matrix[0].size();
        for(int i=0;i<m;++i){
            if (matrix[i][0]==0)
                flag=true;
            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[0][j]==0 || matrix[i][0]==0)
                    matrix[i][j]=0;
            }
            if(flag)
                matrix[i][0]=0;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23