LeetCode中二维数组如何实现零矩阵

在LeetCode中，零矩阵（Zero Matrix）是一个常见的算法问题。给定一个二维数组（矩阵），如果某个元素为0，则将其所在的行和列的所有元素都设置为0。本文将介绍如何实现这一功能。

问题描述

给定一个 m x n 的矩阵，如果矩阵中的某个元素为0，则将其所在的行和列的所有元素都设置为0。要求在原矩阵上进行修改，不使用额外的空间。

解决思路

1. 标记法：

   • 首先遍历矩阵，找到所有值为0的元素，并记录它们所在的行和列。
   • 然后再次遍历矩阵，将标记的行和列中的所有元素设置为0。

2. 原地修改：

   • 使用矩阵的第一行和第一列来记录是否需要将对应的行或列设置为0。
   • 首先检查第一行和第一列是否需要设置为0。
   • 然后遍历矩阵的其他部分，如果某个元素为0，则将其所在的行和列的第一个元素设置为0。
   • 最后根据第一行和第一列的标记，将对应的行和列设置为0。

代码实现

def setZeroes(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
    
    # 根据标记设置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

总结

通过使用矩阵的第一行和第一列来记录需要设置为0的行和列，我们可以在不使用额外空间的情况下实现零矩阵。这种方法的时间复杂度为O(m*n)，空间复杂度为O(1)，是一种高效的解决方案。