🥈 73. 矩阵置零

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

进阶：

• 一个直观的解决方案是使用的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

示例 1：

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

示例 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]]

提示：

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

题解

这道题还是 比较容易的，因为只要一个坐标为0，整行、列坐标就是0，所以需要额外的空间去标记元素的状态。因为整行或者整列置0，所以不需要给每个元素标记状态，因此不需要的空间，只需要标记行状态和列状态，也就是空间。

使用标记数组

Python

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m=[0]*len(matrix)
        n=[0]*len(matrix[0])
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    m[i]=n[j] = 1
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if m[i] == 1 or n[j] == 1:
                    matrix[i][j] = 0

JavaScript

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    let m = new Array(matrix.length).fill(0)
    let n = new Array(matrix[0].length).fill(0)
    for(let i = 0;i < matrix.length;i++){
        for(let j = 0;j < matrix[0].length;j++ ){
            if (matrix[i][j] === 0){
                m[i] = n[j] = 1
            }
        }
    }
    for(let i = 0;i < matrix.length;i++){
        for(let j = 0;j < matrix[0].length;j++ ){
            if (m[i] == 1 || n[j] == 1){
                matrix[i][j] = 0    
            }
        }
    }
};

复杂度分析

• 时间复杂度：，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。

• 空间复杂度：，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。

使用两个标记变量