【第三轮】6.16-6.22 CareerCup 1.7

serolins 发表于 2014-6-22 10:49
【解题思路】
书中的答案用了O(M+N)，其实可以做的更好，如同@bearkino的方法。使用第0行和第0列其实就可 ...

【解题思路】traverse the matrix and track whether the row/col should set to 0 or not, then use another loop to set zero
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link】https://gist.github.com/yupingzhang/9b0c7e18118728f8dfd7

【解题思路】先统计zero的行列，后setzero
【时间复杂度】O(MN)
【空间复杂度】O（M+N）
【gist link】https://gist.github.com/guchang/485043d45984a5c16d5b

遍历数组把是零的元素位置记下，然后根据记下的位置遍历一边数组把相应的行列设为零
时间复杂度：　Ｏ（ＭN）
空间复杂度：Ｏ（Ｍ+N）
gist : https://gist.github.com/daisyang/6a931c5dc1681de5336e

habina 发表于 2014-6-16 17:06
【解题思路】
  Collect all indices that elements are zero
  Set element to zero where the element' ...

能解释下为什么空间复杂度是１吗

daisyang 发表于 2014-6-23 00:08
能解释下为什么空间复杂度是１吗

不好意思，也许我写错了

【解题思路】Check the first row and first column and determine if they need to be set as 0. Then use the first row and first column to record if a column or a row need to be set as 0.
【时间复杂度】O(MN)
【空间复杂度】O（1）
【gist link】https://gist.github.com/nealhu/f09c33f6003fc55e35ff

【解题思路】scan the whole matrix and use two boolean arrays to track which row and column will be zero. scan the whole matrix again and set element to zero based on the two boolean arrays
【时间复杂度】O(MN)
【空间复杂度】O（M+N）
【gist link】https://gist.github.com/pchong90/93ffd472a6027d3b7a6a

【解题思路】和前面大多数一样，一个是另用两个boolean array存哪行或列有0，然后再根据这个把相应的行、列里的数都变成0.
【时间复杂度】O(MN)
【空间复杂度】O（M+N）
【解题思路】leetcode大神解法，不需要另外用两个boolean array,就直接把信息存在第一行和第一列，但之前需要存下第一行、列是否本身就有0，如果有，最后的时候把他们自己全变0.
【时间复杂度】O(MN)
【空间复杂度】O（1）
【gist link】https://gist.github.com/XiaoxiaoLi/79a7db7dd595df313342

【解题思路】Use two boolean variables to keep record of the existence of 0 in first row and first column. Go through all other cells in matrix and update corresponding first row or column cell to 0 if it is 0. Use the information from first row and first column to update all other cells in reverse. At last, update first row and first column based on boolean variables.
【时间复杂度】O(M*N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/e03795a0a6bb926aad77