【第三轮】6.16-6.22 CareerCup 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】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

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

【解题思路】
LeetCode原题。
1. 设两个bool变量，一个用来描述第行是否有零；另一个用来描述第一列是否有零。
2. 遍历整个matrix，如果某一个元素是0，则把它所在的行的第一个元素设为0，并把它所在的列的第一个元素设为0。
3. 根据第一行和第一列里面的0，把对应的行和列都设为0。
4. 根据第一步中的两个变量，把第一行和第一列设为0。
【时间复杂度】
O(mn)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_7-cc
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】两次遍历，第一次记录零所在的行列，第二次置零
【时间复杂度】O（MN）
【空间复杂度】O（M+N）
【gist link】https://gist.github.com/weazord/56924e3c39d5b898251

Test 1

Original:

1        0       

0        1       

Zeroes Set:

0        0       

0        0       

Test 2

Original

1        2        0        4        5       

6        7        8        9        10       

11        12        13        14        15       

16        17        18        19        20       

Zeroes Set:

0        0        0        0        0       

6        7        0        9        10       

11        12        0        14        15       

16        17        0        19        20       

Test 3

Original

1        2        3        4        5        6       

7        8        0        10        11        12       

13        14        15        16        0        18       

19        20        21        22        23        24       

25        26        27        28        29        30       

Zeroes Set:

1        2        0        4        0        6       

0        0        0        0        0        0       

0        0        0        0        0        0       

19        20        0        22        0        24       

25        26        0        28        0        30       

【解题思路】
     if a[i,j]=0; a[i,0]=0; a[0,j]=0;
   然后
     i>0, j>0时：再遍历a[i,0]和a[0,j]，如果a[..]=0,那么设该行或该列为0
    i=0(j=0)时，check一下是本来就是有零，还是后面设的~如果是前者的话，将该行（or 列）设为全零
【时间复杂度】o(mn)
【空间复杂度】o(m+N)....其实我不懂为啥是这个复杂度...
【gist link】
https://gist.github.com/jaly50/9a2ec0ca4d7d4f31eabf
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
Original matrix is:
  1  4  4
  2  0  8
  1  3  2
  0 21 32

Set zero of the entire row and column:
  0  0  4
  0  0  0
  0  0  2
  0  0  0

【解题思路】
Assume this problem want us to set 0 according the initial matrix.
Simplest method: create a MxN matrix to store where 0 appear, then according it, we can set the row and column. Additional space is O(MN), runtime is O(MN), since we must scan the whole matrix, we cannot optimize the runtime.
To optimize the space, the aim is to set row and column, so we only need to store whether there are 0 in the row/column, thus the space is O(M+N).
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/qianhuang/b93ec80f0ad06cfeb0fc

【解题思路】
  Collect all indices that elements are zero
  Set element to zero where the element's horizontal or vertical index appears in the collection
【时间复杂度】
  O(NM)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/habina/7cab9ec45a5bf766cce3

【解题思路】
same to the one on book
【时间复杂度】
N^2
【空间复杂度】
N
【gist link】
https://gist.github.com/gaoyike/bf57c6e80674c04d44b2

【解题思路】
same to the one on book
【时间复杂度】
O(mn)
【空间复杂度】
O(m+n)
【gist link】
https://gist.github.com/JoyceeLee/19a09295137e1b537987

【解题思路】
two boolean arrays, one to tag the row which has 0s, and another to tag the column which has 0s. second pass is to set matrix[j] = 0 if row or column has zeros.
【时间复杂度】
O(M*N)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/iwilbert/9a6463330ddf8ac34b61

【解题思路】Use two extra boolean arrays to record which rows and cols should be set to 0.
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link】https://gist.github.com/chouclee/1ba6e45c932413c8b401

【解题思路】find rows and columns where zeros lie, then set zeros to corresponding rows and columns
【时间复杂度】O(mn)
【空间复杂度】O(n)
【gist link】https://gist.github.com/startupjing/06c91feafb652793cfe8

【解题思路】Same to previous posters.
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/849a31e739c234a7555e.git