【第四轮】3.30 -4.5 Career Cup 1.7

1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row
and column are set to 0.

请参加活动的童鞋跟帖回复自己的解法，回复请参考以下格式：

解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎探讨各种follow up questions，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

import java.util.Set;
import java.util.HashSet;
import java.awt.Point;

class SetZero {
  public static void main(String[] args){
    int[][] T = {{0,1,1,1,1}, {2,2,2,2,2}, {3,3,3,3,0}};
    print(T);
    Set<Point> S = findZero(T);
    System.out.println(S);
    solve(T);
    print(T);
  }

  public static void print(int[][] matrix){
    int w = matrix[0].length, h = matrix.length;
    for (int y = 0; y < h; ++y) {
      for (int x = 0; x < w; ++x) {
        System.out.print(matrix[y][x]);
      }
      System.out.print("\n");
    }
  }
  //given a point, set its row and column to zeros
  public static void setZero(int[][] matrix, int x0, int y0){
    int h = matrix.length;
    int w = matrix[0].length;
    for(int x = 0; x < w; ++x){
      matrix[y0][x] = 0;
    }
    for(int y = 0; y < h; ++y){
      matrix[y][x0] = 0;
    }
  }
  public static Set<Point> findZero(int[][] matrix){
     int w = matrix[0].length, h = matrix.length;
     Set<Point> zeros = new HashSet<Point>();
     for(int y = 0; y < h; ++y){
        for(int x =0; x < w; ++x){
          if(matrix[y][x] == 0){
            zeros.add(new Point(x,y));
          }
        }
     }
     return zeros;
  }

  public static void solve(int[][] matrix){
    for(Point s: findZero(matrix)){
      setZero(matrix,s.x,s.y);
    }
  };
}

//Solution1
// 如果矩阵如果有元素为0，就把对应的行和列上面的元素都置为0。
// 这里最大的问题就是我们遇到0的时候不能直接把矩阵的行列在当前矩阵直接置0，
// 否则后面还没访问到的会被当成原来是0，最后会把很多不该置0的行列都置0了。
// 一个直接的想法是备份一个矩阵，然后在备份矩阵上判断，
// 在原矩阵上置0，这样当然是可以的，不过空间复杂度是O(m*n)，不是很理想。

//Solution2
// 我们看到其实判断某一项是不是0只要看它对应的行或者列应不应该置0就可以，
// 所以我们可以维护一个行和列的布尔数组，然后扫描一遍矩阵记录那一行或者列是不是应该置0即可，
// 后面赋值是一个常量时间的判断。这种方法的空间复杂度是O(m+n)

//Solution3
// 我们考虑使用第一行和第一列来记录上面所说的行和列的置0情况，
// 这里问题是那么第一行和第一列自己怎么办？想要记录它们自己是否要置0，
// 只需要两个变量（一个是第一行，一个是第一列）就可以了。
//然后就是第一行和第一列，如果要置0，就把它的值赋成0（反正它最终也该是0，无论第一行或者第一列有没有0），否则保留原值。
// 然后根据第一行和第一列的记录对其他元素进行置0。最后再根据前面的两个标记来确定是不是要把第一行和第一列置0就可以了。
// 这样的做法只需要两个额外变量，所以空间复杂度是O(1)。
// 时间上来说上面三种方法都是一样的，需要进行两次扫描，
// 一次确定行列置0情况，一次对矩阵进行实际的置0操作，所以总的时间复杂度是O(m*n)

https://gist.github.com/JamesJi9277/aee07981770df9840054

【解题思路】
* First, we at least need two loops, one for finding out the rows and columns containing 0,
* the other one to set 0. We cannot do it in one loop, because it will influence result.
* We set the row and column which contain 0, true.
* Then in the next loop, if row or column is true, we set it 0.
*
* Note: "or" is very important here, think about it. I used three loops initially, which is not most efficient.
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/leonw007/47cf3244fea404e21562
【test case】included in the link above

好像很不错的活动，规则是什么？

Pony_s 发表于 2015-3-30 17:41
好像很不错的活动，规则是什么？

详情请见本版置顶帖~~

  解题思路】
Using two loops to record the zero positions and then set values
Using two set to store the zeroRow and zeroCol
【时间复杂度】
O(N^2)
【空间复杂度】
O(N)
【gist link]
https://gist.github.com/zhangjiang2013/bd5f3102776e54b97622
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

【解题思路】
we only need know  which row and  column to be set to  0
  so  we need  set two boolean array to  mark the    rows and columns should be set to  0
【时间复杂度】
O(N*M)
【空间复杂度】
O(N+M)
【gist link]
https://gist.github.com/michaelniu/cbeb9826a8c8d040fe9e

[solution]
use two flags to indicate if the first row & col need to be reset. use the first row&col to record if the corresponding row or col need to be reset. This reduces the space complexity to O(1)
[time]
O(mn)
[space]
O(1)
[gist]
https://gist.github.com/A30041839/af34e4ffa18b39c57a16

[solution]
用两个变量来记录第一行和第一列是否需要置零；用第一行和第一列来记录每一行和每一列是否需要置零；扫两边矩阵，第一遍用来记录哪一行需要置零，第二遍用来置零。
[time]
O(mn)
[space]
O(1)
[gist]
https://gist.github.com/chongtianzs/a7eb6914e0fb21e8e054

【解题思路】
建立两个新数组，一个记录需要置0的行，一个记录需要置0的列，扫两遍矩阵，第一次标记置零的列和行，第二次执行置零操作
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/alikewmk ... -1-7-crosszero-java