矩阵置零

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     */
    void setZeroMatrix(vector<vector<int> >& matrix) 
    {
        // write code here
        int r=matrix.size(), c=matrix[0].size();
        vector<bool> row(r), col(c);
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(matrix[i][j]==0)
                {
                    row[i]=col[j]=true;
                }
            }
        }
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(row[i]||col[j])
                {
                    matrix[i][j]=0;
                }
            }
        }
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     */
    void setZeroMatrix(vector<vector<int> >& matrix) {
        // write code here
        int m=matrix.size(), n=matrix[0].size();
        vector<vector<bool>>dp(m,vector<bool>(n, false));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==0&&!dp[i][j]){
                    reset(matrix, i, j, m ,n, dp);
                }
            }
        }
    }
    void reset(vector<vector<int>>& matrix, int row, int col, int m, int n, vector<vector<bool>>& dp){
            for(int i=0;i<n;i++){
                if(matrix[row][i]!=0)
                    dp[row][i]=true;
                matrix[row][i]=0;
            }
            for(int i=0;i<m;i++){
                if(matrix[i][col]!=0)
                    dp[i][col]=true;
                matrix[i][col]=0;
            }
    }
};

# -*- 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)