073 - Set Matrix Zeroes

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(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?

Hide Tags

Array

 

要求in place，所以必须用已经存在的空间，也就是matrix里头的单元。

当找到第一个0的时候，就可以用它所在的行和列作为buffer，

把其他的零所在的行列，也就是需要置0的行列，在这两个buffer里，标识出来。

注意最后置位的时候，要先留住buffer里的内容，不然会把整个矩阵都置为0.

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int sz=matrix.size();
        if(sz)
        {
            int zz=matrix[0].size();
            if(zz)
            {
                for(int ii=sz-1; ii>=0; ii--)
                    for(int jj=zz-1; jj>=0; jj--)
                       if(0 == matrix[ii][jj])
                            return clean(matrix, ii, jj, sz, zz); //直接return就好
            }
       }
    }
   
    void clean(vector<vector<int>>& matrix, int buf_row, int buf_col, int sz, int zz)
    {
        for(int ii=buf_row-1; ii>=0; ii--)
            for(int jj=zz-1; jj>=0; jj--)
                //reuse the row/col of first zero as a buffer for zeros
                if((buf_col!=jj)&&(0 == matrix[ii][jj]))
                {
                    matrix[buf_row][jj]=0;
                    matrix[ii][buf_col]=0;
                }

        //now set all zeros
        for(int ii=sz-1; ii>=0; ii--)
            if((ii!=buf_row)&&(0==matrix[ii][buf_col])) //先不要set用作缓冲区的行
                for(int jj=zz-1; jj>=0; jj--)
                    matrix[ii][jj] = 0;

        for(int jj=zz-1; jj>=0; jj--)
            if(0==matrix[buf_row][jj])
              for(int ii=sz-1; ii>=0; ii--)
                matrix[ii][jj] = 0;

        for(int jj=zz-1; jj>=0; jj--) //单独set用做缓冲区的行，不然中间的循环会多set
            matrix[buf_row][jj] = 0;

        return;
    }
};