[Leetcode][python]Set Matrix Zeroes/矩阵置零

怼烎@ 2022-06-07 10:51 171阅读 0赞

## 题目大意 ##

如果矩阵中存在0，那么把0所在的行和列都置为0。要求在所给的矩阵上完成操作。  
注意：最好的空间复杂度是常数空间

## 解题思路 ##

参考：  
[https://www.hrwhisper.me/leetcode-set-matrix-zeroes/][https_www.hrwhisper.me_leetcode-set-matrix-zeroes]  
[https://shenjie1993.gitbooks.io/leetcode-python/073%20Set%20Matrix%20Zeroes.html][https_shenjie1993.gitbooks.io_leetcode-python_073_20Set_20Matrix_20Zeroes.html]

思路：  
1.创建一个矩阵的拷贝，然后根据这个拷贝进行判断O(MN)  
2.创建一个数组，记录矩阵为0的行和列下标O(m+n)  
3.把有0的元素映射到首行和首列O(c)：详解看代码

## 代码 ##

这里的复杂度是**空间复杂度**

### O(c) ###

class Solution(object):
        def setZeroes(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: void Do not return anything, modify matrix in-place instead.
            """
            first_row = False
            first_col = False
            m = len(matrix)
            n = len(matrix[0])
            # 第一列若有0，first_col = True
            for i in range(m): 
                if matrix[i][0] == 0:
                    first_col = True
            # 第一行若有0，first_row = True
            for j in range(n):
                if matrix[0][j] == 0:
                    first_row = True
            # 若中间有0，同时映射到首行首列
            for i in range(1, m):
                for j in range(1, n):
                    if matrix[i][j] == 0:
                        matrix[i][0] = matrix[0][j] = 0
            # 然后通过首行首列，将所有改为0的置为0
            for i in range(1, m):
                for j in range(1, n):
                    if matrix[0][j] == 0 or matrix[i][0] == 0:
                        matrix[i][j] = 0
            # 最后再把保存好的首行首列是否改为0的信息拿出来置为0
            if first_row:
                for j in range(n):
                    matrix[0][j] = 0
            if first_col:
                for i in range(m):
                    matrix[i][0] = 0

### O(m+n) ###

class Solution:
        # @param matrix, a list of lists of integers
        # RETURN NOTHING, MODIFY matrix IN PLACE.
        def setZeroes(self, matrix):
            m , n = len(matrix), len(matrix[0])
            row , col = [0 for i in range(m)] , [0 for i in range(n)]
            for i in range(m):
                for j in range(n):
                    if not matrix[i][j]:
                        row[i]=col[j]=1
            for i in range(m):
                if row[i]:
                    for j in range(n):
                        matrix[i][j]=0
    
            for j in range(n):
                if col[j]:
                    for i in range(m):
                        matrix[i][j]=0

### O(mn) ###

class Solution:
        # @param matrix, a list of lists of integers
        # RETURN NOTHING, MODIFY matrix IN PLACE.
        def setZeroes(self, matrix):
            m , n = len(matrix), len(matrix[0])
            temp = [[matrix[i][j] for j in range(n)] for i in range(m)]
            for i in range(m):
                for j in range(n):
                    if not temp[i][j]:
                        self.setZero(i,j,n,m,matrix)
    
        def setZero(self,row,col,n,m,matrix):
            for i in range(m):
                matrix[i][col]=0
            for j in range(n):
                matrix[row][j]=0

## 总结 ##

[https_www.hrwhisper.me_leetcode-set-matrix-zeroes]: https://www.hrwhisper.me/leetcode-set-matrix-zeroes/
[https_shenjie1993.gitbooks.io_leetcode-python_073_20Set_20Matrix_20Zeroes.html]: https://shenjie1993.gitbooks.io/leetcode-python/073%20Set%20Matrix%20Zeroes.html