当前位置：首页 > article >正文

LeetCode 热题 100 73. 矩阵置零

article 2025/2/26 20:23:35

LeetCode 热题 100 | 73. 矩阵置零

大家好，今天我们来解决一道经典的算法题——矩阵置零。这道题在LeetCode上被标记为中等难度，要求我们将矩阵中为0的元素所在的行和列全部置为0。下面我将分别给出非原地算法和原地算法的Python代码实现，并进行对比分析。

问题描述

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

示例：

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

非原地算法代码

思路

使用两个额外的数组 rows 和 cols 来记录需要置零的行和列。
遍历矩阵，记录所有值为 0 的元素所在的行和列。
根据记录的行和列，将矩阵中对应的行和列全部置为 0。

代码实现

def setZeroes_non_inplace(matrix):
    m, n = len(matrix), len(matrix[0])
    rows = [False] * m  # 记录需要置零的行
    cols = [False] * n  # 记录需要置零的列

    # 遍历矩阵，记录需要置零的行和列
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                rows[i] = True
                cols[j] = True

    # 根据记录置零
    for i in range(m):
        for j in range(n):
            if rows[i] or cols[j]:
                matrix[i][j] = 0

# 测试示例
matrix1 = [[1,1,1],[1,0,1],[1,1,1]]
matrix2 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

setZeroes_non_inplace(matrix1)
setZeroes_non_inplace(matrix2)

print(matrix1)  # 输出: [[1,0,1],[0,0,0],[1,0,1]]
print(matrix2)  # 输出: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

原地算法代码

思路

利用矩阵的第一行和第一列来标记需要置零的行和列。
需要额外处理第一行和第一列本身是否包含 0。

代码实现

def setZeroes_inplace(matrix):
    m, n = len(matrix), len(matrix[0])
    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))

    # 使用第一行和第一列来标记是否需要置零
    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

    # 根据标记置零
    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

    # 处理第一行和第一列
    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

# 测试示例
matrix1 = [[1,1,1],[1,0,1],[1,1,1]]
matrix2 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

setZeroes_inplace(matrix1)
setZeroes_inplace(matrix2)

print(matrix1)  # 输出: [[1,0,1],[0,0,0],[1,0,1]]
print(matrix2)  # 输出: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]