LeetCode 热题 100 73. 矩阵置零

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

非原地算法代码

思路

1. 使用两个额外的数组 rows 和 cols 来记录需要置零的行和列。
2. 遍历矩阵，记录所有值为 0 的元素所在的行和列。
3. 根据记录的行和列，将矩阵中对应的行和列全部置为 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]]

原地算法代码

思路

1. 利用矩阵的第一行和第一列来标记需要置零的行和列。
2. 需要额外处理第一行和第一列本身是否包含 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]]

代码对比

非原地算法

• 优点：
  • 逻辑简单，易于理解和实现。
  • 不需要修改原始矩阵的额外信息。
• 缺点：
  • 使用了额外的空间 O(m + n) 来存储需要置零的行和列。

原地算法

• 优点：
  • 空间复杂度为 O(1)，完全原地操作。
• 缺点：
  • 逻辑稍复杂，需要额外处理第一行和第一列。

总结

• 非原地算法：逻辑简单，适合对空间复杂度要求不高的场景。
• 原地算法：空间复杂度低，适合对空间要求严格的场景。

根据实际需求选择合适的方法即可。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！