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

Example 1:

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

  • 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?
思路         这道题最简单的就是使用O(m*n)的空间来解决问题，但是空间浪费太高。我们可以先对矩阵进行遍历，将0出现的位置的行坐标和列坐标分别记录下来。然后当遍历完毕之后我们根据行坐标和列坐标来设置0.得到最后的结果。时间复杂度为O(m*n), 空间复杂度为O(m+n)。 另外在题中，提到使用O(1)的空间也可以解决问题，我没能想出来，看了参考答案之后明白了他在遇到元素0的时候，先将该元素所对应的行的第一个元素和对应列的第一个元素设置为0,然后遍历结束之后判断首行元素的的值状态将剩余的部分设置为0.最后得到结果。
   解决代码 
 1 class Solution(object):  2     def setZeroes(self, matrix):  3         """
 4  :type matrix: List[List[int]]  5  :rtype: None Do not return anything, modify matrix in-place instead.  6         """
 7         if not matrix:  8             return matrix  9         row, cloum = len(matrix), len(matrix[0]) 10         tem_row, tem_cloum = set(), set() 11         for i in range(row): #遍历矩阵得到0的行坐标和列左边 12             for j in range(cloum): 13                 if matrix[i][j] == 0: 14  tem_row.add(i) 15  tem_cloum.add(j) 16  self.set_zero(matrix, tem_row, tem_cloum) # 进行0设置 17                      
22     def set_zero(self, matrix, tem_row, tem_cloum): 23         for row  in tem_row: # 设置列 24             for i in range(len(matrix[0])): 25                 if matrix[row][i] != 0: 26                     matrix[row][i] = 0 27         for cloum  in tem_cloum: # 设置行 28             for j in range(len(matrix)): 29                 if matrix[j][cloum] != 0: 30                      matrix[j][cloum] = 0

常量空间的解法

　　详细解释链接：https://leetcode.com/problems/set-matrix-zeroes/solution/

 1 class Solution(object):  2     def setZeroes(self, matrix):  3         """
 4  :type matrix: List[List[int]]  5  :rtype: void Do not return anything, modify matrix in-place instead.  6         """
 7         is_col = False  8         R = len(matrix)  9         C = len(matrix[0]) 10         for i in range(R): # 遍历矩阵，得到元素为0的地址，并设置该列和该行起始位置为0， 11             if matrix[i][0] == 0: 12                 is_col = True 13             for j in range(1, C): 14                 if matrix[i][j]  == 0: 15                     matrix[0][j] = 0 16                     matrix[i][0] = 0 17 
18    
19         for i in range(1, R): # 根据行的开头和列的开头来设置剩余部分的元素值 20             for j in range(1, C): 21                 if not matrix[i][0] or not matrix[0][j]: 22                     matrix[i][j] = 0 23      
24         if matrix[0][0] == 0: # 判断起始位置是否为0 25             for j in range(C): 26                 matrix[0][j] = 0 27 
28         if is_col: # 第一列全为0 29             for i in range(R): 30                 matrix[i][0] = 0
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄