Set Matrix Zeroes

Myth丶恋晨 2021-12-17 10:45 154阅读 0赞

Given a *m* x *n* matrix, if an element is 0, set its entire row and column to 0. Do it in place.

[click to show follow up.][]

**Follow up:**

Did you use extra space?  
A straight forward solution using O(*m**n*) space is probably a bad idea.  
A simple improvement uses O(*m* \+ *n*) space, but still not the best solution.  
Could you devise a constant space solution?

cc150的题目,但是这里要求O(1)空间.

解法1自带魔法的python:

这题python因为可以不限定类别,所以可以作弊,先用别的字符'\#'替代需要替换的0,防止阻碍其余要替换的0,也防止新引入的'0',使矩阵全部置0.

class Solution(object):
        def setZeroes(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: void Do not return anything, modify matrix in-place instead.
            """
            if not matrix or not matrix[0]:
                return 
            m = len(matrix)
            n = len(matrix[0])
            
            for i in xrange(m):
                for j in xrange(n):
                    if matrix[i][j] == 0:
                        for k in xrange(m):
                            if matrix[k][j] != 0:
                                matrix[k][j] = '#'
                        for k in xrange(n):
                            if matrix[i][k] != 0:
                                matrix[i][k] = '#'
            for i in xrange(m):
                for j in xrange(n):
                    if matrix[i][j] == '#':
                        matrix[i][j] = 0
            return

用第一行,第一列存储行列是否为0的信息.

对于原本用O(m+n)空间保存每行每列是否置0的信息的做法,我们可以做改进.即用数组本身的第一行第一列来保存这个这个信息.每行的第一个开始代表改行是否要全部置0,全部置0则在这格保存0, 否则其他数.每列的第一行同样如此.但是第一行第一列如此做会有冲突,所以最佳的办法是另取一个变量保存冲突的第一行或者第一列.  
这里把第一行第一列的数字保存为行是否有0.

繁琐写法:

class Solution(object):
        def setZeroes(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: void Do not return anything, modify matrix in-place instead.
            """
            if not matrix or not matrix[0]:
                return 
            m = len(matrix)
            n = len(matrix[0])
            
            fc = False #whether first column contains 0
            for i in xrange(m):  # the first column will be used to stored whether 0 exist in a row, so we must find whether 0 exist in the first column in advance. 
                if not matrix[i][0]:
                    fc = True
                    break
            for i in xrange(m):   #every row
                if 0 in matrix[i]:
                    matrix[i][0] = 0
            for j in xrange(1,n): #every column except the first one
                if 0 in [matrix[i][j] for i in xrange(m)]:
                    matrix[0][j] = 0
                    
            for j in xrange(1,n): #every column except the first one
                if not matrix[0][j]:
                    for i in xrange(1,m):
                        matrix[i][j] = 0
                        
            for i in xrange(m):  #set every row except the fi
                if not matrix[i][0]:
                    for j in xrange(1,n):
                        matrix[i][j] = 0
           
            if fc:
                for i in xrange(m):
                    matrix[i][0] = 0
            
            return

简化写法,简直机智:

class Solution(object):
        def setZeroes(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: void Do not return anything, modify matrix in-place instead.
            """
            if not matrix or not matrix[0]:
                return 
            m = len(matrix)
            n = len(matrix[0])
            fc = -1
            for i in xrange(m):
                if not matrix[i][0]: fc = 0
                for j in xrange(1,n):
                    if not matrix[i][j]:
                        matrix[i][0] = 0
                        matrix[0][j] = 0
            for i in xrange(m-1,-1,-1):
                for j in xrange(n-1,0,-1): #first colunm is trackled beside.
                   if (not matrix[i][0]) or (not matrix[0][j]):
                       matrix[i][j] = 0
                if not fc: matrix[i][0] = 0 #tackle first colunm
            return

转载于:https://www.cnblogs.com/sherylwang/p/5919113.html

[click to show follow up.]: https://leetcode.com/problems/set-matrix-zeroes/#