73. Set Matrix Zeroes -M

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

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

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

A:

Method 1:        O(m+n) space, using two linked list to record where the zeros occurred

public class Solution {
      public void setZeroes(int[][] matrix) {
            // Use linked list to record where zeros occurs
          if(matrix == null || matrix.length ==0)
              return;
          
          int m = matrix.length, n = matrix[0].length;
          List rowList = new LinkedList<Integer>();
          List colList = new LinkedList<Integer>();
          for(int i =0;i<m;i++){
              for(int j =0;j<n; j++){
                  if(matrix[i][j] == 0){
                      rowList.add(i);
                      colList.add(j);
                  }
              }
          }
          // set row to zeros
          for(int i : rowList)

              Arrays.fill(matrix[i],0);
          
          for(int j : colList)
              for(int i =0;i<m;i++)
                  matrix[i][j]=0;
              
        }
}

 -------------------------------------下面的方法，是在网上找的---------------
常数空间的话，第一可以考虑是不是固定数量的几个变量能搞定；否则可以考虑是不是问题本身已经提供了足够的空间。
这道题属于后者，就是利用矩阵的第一行和第一列来作为辅助空间使用。不用开辟新的存储空间。方法就是：
1.. 找到第一个0， 该行和列就可以用来做标记, 用row0, col0 来表示

2.扫描剩下的矩阵元素，如果遇到了0，就将对应的第一行和第一列上的元素赋值为0
这里不用担心会将本来第一行或第一列的1改成了0，因为这些值最后注定要成为0的。

3.根据第一行和第一列的信息，已经可以将剩下的矩阵元素赋值为结果所需的值了
即，拿第一行为例，如果扫描到一个0，就将这一列都清0.

4.根据1中确定的状态，处理第一行和第一列。
如果最开始得到的第一行中有0的话，就整行清零。同理对列进行处理。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // check first row
        bool firstRow0 = false, firstCol0 = false;
        for(int j=0;j<n;++j)
            if(!matrix[0][j])
            {
                firstRow0 = true;
                break;
            }
        for(int i=0;i<m;++i)
            if(!matrix[i][0])
            {
                firstCol0=true;
                break;
            }
        for(int i=1;i<m;++i)
            for(int j=1;j<n;++j)
                if(!matrix[i][j])
                    matrix[0][j] = matrix[i][0] = 0;
        
        // now set all as zero
        for(int i=1;i<m;++i) // check first column
            if(!matrix[i][0])
                fill(matrix[i].begin()+1, matrix[i].end(), 0);
        
        for(int j = 1; j<n;++j)
            if(!matrix[0][j])
                for(int i=1;i<m;++i)
                    matrix[i][j]=0;
        
        if(firstRow0)
            fill(matrix[0].begin(), matrix[0].end(), 0);
        if(firstCol0)
            for(int i =0; i<m;++i)
                matrix[i][0]=0;
    }
};

Mistakes:
1: 对method1， 因为最后的那个 setCol zeros的循环， are copied from above,，though we take GREAT care, we still forget to change the n to m.
2:  method 2 中， 方法的刚开始，我们假设当到了squareLen ==1的时候，就是最后右下角的item. 但是，我们忘记了。当只有一行的时候，squareLen 也是1 的。 -------------------导致这个原因， 有一部分原因，是在于开始，我们对square==1的情况，（当是最后一行或者最后一列时） 我们也要递归调用的。 ----------当然，更重要的是，各种情况考虑不完善，
3：  for loop中的jj ++ 给写成了j ++ . ╮(╯▽╰)╭~~~~~~~~~~~~~~~~~~~~

Learned:

---------------------第二遍，------ 先找到一个不在matrix中出现过的数，然后，扫描所有的0， 并将全部的行列的非零值 设 为那个数字。 。 最后，再把其改成0.

public class Solution {
  
    public void setZeroes(int[][] matrix) {
        // assume Integer.MIN_VALUE is not used in matrix
        int m = matrix.length;
        if (m == 0)
            return;
        int n = matrix[0].length;
        // find special value that does not appear in matrix
        boolean findNonUsed = false;
        int specialVal = 0;
        while (!findNonUsed) {
            findNonUsed = true;
            double up = Integer.MAX_VALUE ;
            double low =  Integer.MIN_VALUE;
            double val = Math.random() * ( up - low) + low ;
            specialVal = (int) val;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (matrix[i][j] == specialVal)
                        findNonUsed = false;
            
        }
        // change row and column into the special value , 
        for (int i = 0; i < m; i++) {
            boolean flag = false; // flag whether this row should be set to zero
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    flag = true;
                    // set j_th column as zero
                    for (int k = 0; k < m; k++)
                        if(matrix[k][j] != 0){
                            matrix[k][j] = specialVal;
                        }
                }
            }
            if (flag)
                for (int j = 0; j < n; j++)
                    matrix[i][j] = specialVal;
        }
        // change all Integer.MIN_VALUE to zero

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == specialVal)
                    matrix[i][j] = 0;

    }
}

------------3rd  Pass ---------------还是第一遍的思路，找个行，列，然后在上面改--------------

public class Solution { 
    public void setZeroes(int[][] matrix) {
        int row0 = -1, col0 = -1;
        int m = matrix.length, n = matrix[0].length;
        for(int i =0;i< m;i++){
            for(int j =0;j<n;j++){
                if(matrix[i][j] != 0)
                    continue;
                if(row0<0){
                    row0 = i;
                    col0 = j;
                }
                matrix[row0][j] = 0;
                matrix[i][col0] = 0;
            }
        }
        if(row0<0) // not found 0 at all
            return;
        // set all rows
        for(int i =0;i<m; i++)
            if(i != row0 && matrix[i][col0]==0)
                Arrays.fill(matrix[i],0);
        //set all columns
        for(int j =0;j<n;j++)
            if(matrix[row0][j]==0)// set the entire column as 0
                for(int i =0;i< m;i++)
                    matrix[i][j] = 0;
                
        Arrays.fill(matrix[row0],0);
    }
} 

Mistakes:
1:忘记check  是否找到过 0