原地算法

image.png

我的原始思路，两个额外的数组分别标记需要置零的行&列。

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        col_flag = [False for i in range(len(matrix[0]))]
        row_flag = [False for i in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    row_flag[i]=True
                    col_flag[j]=True
        for i in range(len(row_flag)):
            if row_flag[i]:
                matrix[i]=[0]*len(matrix[i])
        for i in range(len(col_flag)):
            if col_flag[i]:
                for k in range(len(matrix)):
                    matrix[k][i]=0 
        return matrix

image.png

• 代码优化：

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        r = len(matrix)
        c = len(matrix[0])
        col_flag = [False for i in range(c)]
        row_flag = [False for i in range(r)]
        for i in range(r):
            for j in range(c):
                if matrix[i][j] == 0:
                    row_flag[i]=True
                    col_flag[j]=True
        for i in range(r):
            for j in range(c):
                if row_flag[i] or col_flag[j]:
                    matrix[i][j]=0
        return matrix

image.png

时间复杂度：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.
        """
        r = len(matrix)
        c = len(matrix[0])
        col_flag=False
        row_flag=False
        for j in range(c):
            if matrix[0][j]==0:
                row_flag=True
        for j in range(r):
            if matrix[j][0]==0:
                col_flag=True

        for i in range(1,r):
            for j in range(1,c):
                if matrix[i][j] == 0:
                    matrix[i][0]=0
                    matrix[0][j]=0
        
        for i in range(1,r):
            for j in range(1,c):
                if matrix[i][0]==0 or matrix[0][j]==0:
                    matrix[i][j]=0
        if row_flag:
            for i in range(c):
                matrix[0][i]=0
        if col_flag:
            for i in range(r):
                matrix[i][0]=0
        return matrix

image.png