【第三轮】6.16-6.22 CareerCup 1.7

【解题思路】两次遍历，第一次记录flag，第二次根据flag设置矩阵
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link】https://gist.github.com/asdw3276/fda81d69ab0bc1b0bb3b

【解题思路】
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/hilda8519/2d76dc3a2bb10751c167

【解题思路】
use the first row and first column to record which row or column should be zero.   need some pre-process to record whether the first row or the first column have any zeroes.
【时间复杂度】
O(M*N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/jyhjuzi/af7a2e0a10787a06fb8b

【解题思路】
Keep two status sets tracking whether a row or column contains zero, and do in place replacement of zeros according to status sets.

【时间复杂度】
O(MN) for go through matrix twice
was stupidly trying to find some O(Max(M,N)) algo for an hour...
【空间复杂度】
O(M+N)

【gist link】
https://gist.github.com/chrislukkk/fd880801c2c56e28e2dc

【解题思路】
a routine way:
use two sets to record where the element is zero,
then clear those rows and columns
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329

【解题思路】
随机生成一个（0~9）的二维数组（M*N），并复制该数组，遍历原数组，找到0的下标i , j，并将新数组对应的i行和j列置0。
【时间复杂度】

【空间复杂度】

【gist link】
https://gist.github.com/ba245a6dd03dde387e60.git

【解题思路】两次遍历，第一次记录零所在的行列，第二次置零
【时间复杂度】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       

【解题思路】
首先，先检查第一行和第一列，有0的话标记为true，然后检查matrix里面的元素，有0的话就在第一行或者第一列标记0. 然后set zero的时候，先检查第一行或者第一列是否有0，有的话就把对应的行列归零；然后检查是否有true， 有的话再把第一行或者第一列归零。结束。
【时间复杂度】
O（MN）
【空间复杂度】
O（1）
【gist link】
https://gist.github.com/UncleGarden/64c7132968c6c205605a

【解题思路】Traverse the matrix, find the zero row and column, then set the columns and rows' elements as 0
【时间复杂度】O(MN)
【空间复杂度】O（M+N）
【gist link】https://gist.github.com/bitcpf/91139d9c1a058eee5258