LeetCode73. 矩阵置零

题目来源：力扣（LeetCode）

题目描述:
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

  

 

  
1
  
2
 

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

  

 

  
1
  
2
 

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

解题思路
使用的是比较常规的解法：两次遍历，第一次记录出现 0 的列，将列的索引保存到 column_zero 集合中，将有零的行全部置 0，同时记录没有 0 出现的行数，将行的索引保存到 row_nonzero 列表中。第二次遍历，只遍历没有 0 出现的行，按照 column_zero 集合中的列索引，进行置 0 。

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        high = len(matrix)
        width = len(matrix[0])
        column_zero = set()    # 保存0的列索引
        row_nonzero = []    # 保存非0行的行索引
        
        for i in range(high):
            temp = 0    # 标志是否有0出现
            for j in range(width):
                if matrix[i][j] == 0:
                    column_zero.add(j)
                    temp = 1
                if j == width - 1:
                    if temp == 1:
                    	# 将该行全部置0
                        matrix[i] = [0 for n in range(width)]
                        continue
                    row_nonzero.append(i)
        for i in row_nonzero:
            for j in column_zero:
                matrix[i][j] = 0
        return matrix

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

文章来源: blog.csdn.net，作者：Dream丶Killer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_43965708/article/details/115074298