[Leetcode] set matrix zeroes 矩阵置零

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

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(m n) 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元素的行、列数，然后根据其所在的记下的行、列将对应行所在的值全赋值为0，但这样会需要O(m+n)的额外空间。所以换一种思路，我们可以遍历数组，若遇到值为0，则将其对应的第一行、第一列的值赋为0，最后根据第一行、第一列的值，更新数组。这样做存在一个问题，那就是，若第一行、第一列中原本就存在0，此时需要更新数组时，如何区分？我们可以先确定第一行、第一列是否存在0，然后，更新完剩下的数组以后，根据是否存在0，决定第一行、第一列的是否全部更新为0。代码如下：

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) 
    {
        int row=matrix.size();
        int col=matrix[0].size();

        if(row==0||col==0)  return;

        bool rFlag=false,cFlag=false;
        for(int i=0;i<row;++i)
        {
            if(matrix[i][0]==0)
            {
                rFlag=true;
                break;
            }
        }    
        for(int i=0;i<col;++i)
        {
            if(matrix[0][i]==0)
            {
                cFlag=true;
                break;
            }
        }

        for(int i=1;i<row;++i)
        {
            for(int j=1;j<col;++j)
            {
                if(matrix[i][j]==0)
                {
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }

        for(int i=1;i<row;++i)
        {
            for(int j=1;j<col;++j)
            {
                if(matrix[i][0]==0||matrix[0][j]==0)
                    matrix[i][j]=0;
            }
        }

        if(rFlag)
        {
            for(int i=0;i<row;++i)
                matrix[i][0]=0;
        }
        if(cFlag)
        {
            for(int i=0;i<col;++i)
                matrix[0][i]=0;
        }

    }
};

代码参考了Gradyang的博客