矩阵置零

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix int整型二维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/e77f5c093978493396b22b9bc01af12d?tpId=196&tqId=40442&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：牛客779086678号
    算法：
        设矩阵matrix的行列分别为m, n, 使用rows, cols分别标记行和列是否存在0，存在为True，否则为False
        首次遍历矩阵matrix：
            若matrix[i][j] = 0, 置rows[i], cols[j] = True, True
        再次遍历矩阵matrix，对于坐标(i, j)，如果rows[i]和cols[j]有一个为True，(i, j)所在的行或列存在0，置matrix[i][j] = 0
    复杂度：
        时间复杂度：O(mn), m, n分别为matrix的行和列
        空间复杂度：O(m + n)
    """

    def setZeroMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        # write code here
        m, n = len(matrix), len(matrix[0])
        rows, cols = [False] * m, [False] * n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    rows[i], cols[j] = True, True

        for i in range(m):
            for j in range(n):
                if rows[i]&nbs***bsp;cols[j]: # 坐标(i, j)所在的行或列存在0，
                    matrix[i][j] = 0

        # print matrix


if __name__ == "__main__":
    sol = Solution()

    # matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]

    matrix = [[0, 1, 0], [1, 1, 1], [1, 1, 1], [1, 1, 1]]

    sol.setZeroMatrix(matrix)