73.矩阵置零 python

矩阵置零

题目
- 题目描述
- 示例 1：
- 示例 2：
- 提示：
题解
- 思路分析
- Python 实现代码
- 代码解释
- 提交结果

题目

题目描述

给定一个 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

题解

思路分析

为了在不使用额外空间的情况下完成这个任务，我们可以利用矩阵的第一行和第一列来记录哪些行和列需要被置零。具体步骤如下：

检查第一行和第一列是否有零：我们需要单独检查第一行和第一列中是否包含零，因为稍后我们会用它们来存储其他行和列的信息。
标记需要置零的行和列：遍历整个矩阵，当发现某个元素为零时，将该元素所在的行的第一个元素和该元素所在的列的第一个元素设置为零。
根据标记置零：再次遍历矩阵（从最后一行开始，以避免覆盖第一行和第一列中的标记），如果某一行或某一列的第一个元素为零，则将整行或整列置零。
处理第一行和第一列：最后，根据第一步的结果决定是否需要将第一行或第一列置零。

Python 实现代码

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    
    # Step 1: Check if the first row and first column contain zeros
    first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))
    
    # Step 2: Mark rows and columns that need to be zeroed
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    
    # Step 3: Set matrix elements to zero based on marks
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    
    # Step 4: Handle first row and column
    if first_row_has_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_has_zero:
        for i in range(m):
            matrix[i][0] = 0