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

python力扣73.矩阵置零

article 2025/3/31 19:54:09

给定一个 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³¹ <= matrix[i][j] <= 2³¹ - 1

问题比较简单，重要的是“原地”算法，也就是说需要在原矩阵的基础上进行修改，传进去的是matrix，返回的仍然是matrix。
思路比较直接：用两个数组来分别记录0元素出现的行和列，遍历第一次填充行列数组，遍历第二次，如果判定为在行或在列，就置零。

# 51ms,12.94mb
# 时间复杂度O(MN)
# 空间复杂度O(M+N)
class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        n = len(matrix[0])
        lines = []
        rows = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    lines.append(i)
                    rows.append(j)
        for i in range(m):
            for j in range(n):
                if i in lines or j in rows:
                    matrix[i][j] = 0
        return matrix

这个算法的空间复杂度为O(M+N)，题目进阶要求为想出一个仅使用常量空间的解决方案，也就是不能用到额外的储存空间。那我么可以使用原数组来储存0元素的位置信息。
可以用原数组的第一行第一列储存信息，但对于第一行第一列是否需要被置零，则需额外的两个布尔值来表示，不然会混乱。
思路如下：
1.统计 matrix 第 0 行和第 0 列是否有 0，保存到 row0, col0 中；
2.遍历 matrix[1:M][1:N] 看当前位置是否有 0，如果有 0，则把信息记录到 matrix 的第 0 行以及第 0 列中。
3.根据 matrix 中第 0 行以及第 0 列的 0，将 matrix[1:M][1:N] 对应的行或者列全部置 0；
4.根据 row0, col0 判断第 0 行和第 0 列是否需要全部置 0。

注意：在置零时的先后顺序，如果先处理了第一列和第一行，然后再处理其他位置的元素。这会导致在处理其他位置的元素时，第一行和第一列的标记信息已经被修改，从而无法正确判断哪些行和列需要被置零。因此需要先修改1：M/N，再修改第一行和第一列。

# 11ms 12.81mb
# 时间复杂度O(MN)
# 空间复杂度O(1)
class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        n = len(matrix[0])
        row0 = False
        line0 = False
        for i in range(m):
            if matrix[i][0] == 0:
                line0 = True
        for j in range(n):
            if matrix[0][j] == 0:
                row0 = True
        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 line0:
            for i in range(m):
                matrix[i][0] = 0
        if row0:
            for j in range(n):
                matrix[0][j] = 0

        return matrix