Given a m x n 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?

 

思路：主要考察的是空间复杂度，

方法一：用rowHasZero记录这一行是否有0 存在，用colHaszero记录这一列是否有0存在。后面处理rowHasZero和colHaszero。空间复杂度O（m+n）

class Solution {    public:        void setZeroes(vector
     
      
        > &matrix)        {               size_t row = matrix.size();            if(row == 0)                return;            size_t col = matrix[0].size();            vector
       
         rowHasZero(row, false);             vector
        
          colHasZero(col, false);             for(int i = 0; i < row; i++)            {                   for(int j = 0; j < col; j++)                {                       if(matrix[i][j] == 0)                    {                           rowHasZero[i] = true;                        colHasZero[j] = true;                    }                   }               }               for(int i = 0; i < row; i++)            {                   if(rowHasZero[i])                {                       for(int j = 0; j < col; j++)                    {                           matrix[i][j] = 0;                    }                   }               }               for(int i = 0; i < col; i++)            {                if(colHasZero[i])                {                    for(int j = 0; j < row; j++)                    {                        matrix[j][i] = 0;                    }                }            }        }};
        
       
      
     

 方法二：空间复杂度O（1），用第0行记录列是否有0，用第0列记录行是否有0，先判断行0和列0是否有0，然后处理矩阵，若matrix[i][j]为0，设置matrix[i][0] = 0; matrix[0][j] = 0;，然后根据matrix[i][0]和matrix[0][j]来设置设置相应的行、列为0，最后处理行0，列0.

class Solution {    public:        void setZeroes(vector
     
      
        > &matrix)        {            size_t row = matrix.size();            if(row == 0)                return;            size_t col = matrix[0].size();            bool rowZeroHasZero = false;            bool colZeroHasZero = false;            for(int i = 0; i < col; i++)            {                if(matrix[0][i] == 0)                {                    rowZeroHasZero = true;                    break;                }            }            for(int i = 0; i < row; i++)            {                if(matrix[i][0] == 0)                {                    colZeroHasZero = true;                    break;                }            }            //cout << rowZeroHasZero << endl;            //cout << colZeroHasZero << endl;            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++)            {                if(matrix[i][0] == 0)                {                    for(int j = 0; j < col; j++)                    {                        matrix[i][j] = 0;                    }                }            }            for(int i = 1; i < col; i++)            {                if(matrix[0][i] == 0)                {                    for(int j = 0; j < row; j++)                    {                        matrix[j][i] = 0;                    }                }            }            //handle the first row & first col            if(rowZeroHasZero)            {                for(int j = 0; j < col; j++)                {                    matrix[0][j] = 0;                }            }            if(colZeroHasZero)            {                for(int i = 0; i < row; i++)                {                    matrix[i][0] = 0;                }            }        }};