题目：

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

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?

 

代码：oj测试通过 Runtime: 220 ms

1 class Solution: 2     # @param matrix, a list of lists of integers 3     # RETURN NOTHING, MODIFY matrix IN PLACE. 4     def setZeroes(self, matrix): 5         # none case 6         if matrix is None: 7             return None 8         # dimension of the matrix 9         ROW = len(matrix)10         COL = len(matrix[0])11         # record the status of first row and first column12         first_row_contains_zero = False13         for i in range(COL):14             if matrix[0][i] == 0:15                 first_row_contains_zero = True16         first_col_contains_zero = False17         for i in range(ROW):18             if matrix[i][0] == 0:19                 first_col_contains_zero = True20         # visit the ROW-1 × COL-1 matrix and check zeros21         for row in range(1,ROW):22             for col in range(1,COL):23                 if matrix[row][col] == 0:24                     matrix[row][0] = 025                     matrix[0][col] = 026         # set zero rows and zero columns27         for row in range(1,ROW):28             for col in range(1,COL):29                 if matrix[row][0]==0 or matrix[0][col]==0:30                     matrix[row][col] = 031         if first_row_contains_zero:32             for i in range(COL):33                 matrix[0][i] = 034         if first_col_contains_zero:35             for i in range(ROW):36                 matrix[i][0] = 0

思路：

题目难点在于要求使用常数空间。

方法是先记录矩阵第一列和第一行是否含有0元素；然后利用第一行和第一列来作为其余列和行是否含有0的记录位置，这样就省下了O(m+n)的空间。

这里有一个梗需要说明：

比如matrix[0][j]作为矩阵第j列是否含有0的标志位，这里分两种情况：

1. matrix[0][j]本身为0，则整个j列的元素（包括matrix[0][j]）最后都为0

2. matrix[0][j]不为零，如果j列其余元素有0，则matrix[0][j]为0；如果j列其余元素不含有0，则matrix[0][j]保持原来的值也不为零

相同了上面的trick之后就可以把代码写出来AC了。

主要学习如下的日志：

 

另外，再狗尾续貂，把自己写的第一版代码也附上。

oj测试通过 Runtime: 213 ms

class Solution:    # @param matrix, a list of lists of integers    # RETURN NOTHING, MODIFY matrix IN PLACE.    def setZeroes(self, matrix):           # none case        if matrix is None:            return None        # dimension of the matrix        ROW = len(matrix)        COL = len(matrix[0])        # record zero rows and zero columns        zero_row = [False for i in range(ROW)]        zero_col = [False for i in range(COL)]        for row in range(ROW):            for col in range(COL):                if matrix[row][col] == 0:                    zero_row[row] = True                    zero_col[col] = True        # set zero rows and zero columns        for row in range(ROW):            for col in range(COL):                if zero_row[row] or zero_col[col]:                    matrix[row][col] = 0

感觉这两种代码在效率上差不多。无非就是时间空间互换的问题。

不过既然只牺牲很少的时间，就换来了一些空间，也是不错的，以后可以在工作中记住这个trick。