题目

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

Follow up:

Did you use extra space?
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(m*n)的方法很简单，直接复制矩阵，然后在新的矩阵空间中进行操作即可。
空间复杂度为O(m+n)的方法，则通过两个一维数组来分别记录每一行是否需要变为0。
空间复杂度为O(1)的方法则使用矩阵的第一行和第一列来记录，并使用两个单独的变量来记录第一行和第一列是否需要归零。在进行完矩阵其余部分的归零操作后，再据此对第一行和第一列进行归零操作。

实现

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size(), n=matrix[0].size();
        bool row0=false, col0=false;
        for(int i=0; i<m; i++)
            if(matrix[i][0]==0) col0=true;
        for(int j=0; j<n; j++)
            if(matrix[0][j]==0) row0=true;
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        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 j=1; j<n; j++)
            if(matrix[0][j]==0)
                for(int i=1; i<m; i++)
                    matrix[i][j]=0;
        if(col0)
            for(int i=0; i<m; i++)
                matrix[i][0]=0;
        if(row0)
            for(int j=0; j<n; j++)
                matrix[0][j]=0;
    }
};