[leetcode]Set Matrix Zeroes

新博文地址：[leetcode]Set Matrix Zeroes

新博文中，用了四种算法，时间复杂度都是O(m*n)，空间复杂度分别为O(m*n)，O(m+n)、O(n)、O(1)，FYI

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?

 这道题很有意思，提示中说一个改进是O(m+n)，但是我没想到怎么做的，我的算法的空间复杂度为O(n)

算法思想是：

首先遍历整个matrix，遇到该行有0，则做3件事情:

1. 标记该行有0

2. 记录列号

3. 将该行扫描完之后，将该行所有元素置为0

然后将该数组全部扫描完之后，行已经设置完了，包含0的列号也已经收集完毕了。再根据这个这些列号重新更新数组。

            public void setZeroes(int[][] matrix) {
        		int  m = matrix.length;
              int n = matrix[0].length;
              Set<Integer> columnSet = new HashSet<Integer>();
              int i = 0,j = 0;
              for(; i < m; i++){
              	boolean hasZero = false;
                  for(j = 0; j < n; j++){
                      if(matrix[i][j] == 0){
                          columnSet.add(j);
                          hasZero = true; 
                      }
                  }
                  if(hasZero){
                  	for(int k = 0 ; k < n; k++){
                  		matrix[i][k] = 0;
                  	}
                  }
              }
              for(int column : columnSet){
              	for(int k = 0 ; k < m; k++){
                      matrix[k][column] = 0;
               }
              }
          }

 还有一种优化策略，不需要额外空间。

将columnSet记录在第一行中，如果第一行不包含0，那么跟上面的做法一样。如果第一行包含0，则先不对第一行进行更新处理，留在最后做。

大家感兴趣的可以自己动手做一下；再想一下，如果将columnSet记录在最后一行中是否可行？