打卡群刷题总结0720——矩阵置零

木又AI帮

发布于 2020-07-22 10:17:56

2690

发布于 2020-07-22 10:17:56

题目：73. 矩阵置零

链接：https://leetcode-cn.com/problems/set-matrix-zeroes

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。示例 1: 输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ] 示例 2: 输入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ] 进阶: 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。你能想出一个常数空间的解决方案吗？

解题：

1、遍历，将0所在行和所在列的非0元素用其他数字来替换，最后将所有替换的数字换成0。

代码：

1、常数空间

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        # 常数
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return matrix

        rows = []
        cols = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    for c in range(len(matrix[0])):
                        if matrix[i][c] != 0:
                            matrix[i][c] = -1e9
                    for r in range(len(matrix)):
                        if matrix[r][j] != 0:
                            matrix[r][j] = -1e9

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == -1e9:
                    matrix[i][j] = 0

2、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 + n
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return matrix

        rows = []
        cols = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rows.append(i)
                    cols.append(j)
        rows = list(set(rows))
        cols = list(set(cols))

        for r in rows:
            for j in range(len(matrix[0])):
                matrix[r][j] = 0
        for i in range(len(matrix)):
            for c in cols:
                matrix[i][c] = 0

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-07-20，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历