leetcode Set Matrix Zeroes

leetcode Set Matrix Zeroes

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

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?

题目地址：leetcode Set Matrix Zeroes

题目大意: 给定一个矩阵，如果它其中的某个元素为0，那么该元素所在行和所在列均变为0.

思路：

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

 

Python 方法1

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

 

Python 方法2

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

 

Python 方法3

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """

        m, n, col0_zero = len(matrix), len(matrix[0]), False
        for i in range(m):
            if not matrix[i][0]: col0_zero = True
            for j in range(1, n):
                if not matrix[i][j]:
                    matrix[i][0] = matrix[0][j] = 0

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, 0, -1):
                if (not matrix[i][0]) or (not matrix[0][j]):
                    matrix[i][j] = 0
            if col0_zero: matrix[i][0] = 0

 

C++方法3

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool col0_zero = false; //第一列是否为0
        
        for(int i = 0; i < matrix.size(); ++i){
            if(!matrix[i][0])  col0_zero = true;
            for(int j = 1; j < matrix[0].size(); ++j)
                if(!matrix[i][j])
                    matrix[i][0] = matrix[0][j] = 0;
        }
        
        for(int i = matrix.size() - 1; i >= 0; --i){
            for(int j = matrix[0].size() - 1 ; j >= 1; --j)
                if(!matrix[i][0]  !matrix[0][j])
                    matrix[i][j] = 0;
            
            if(col0_zero) matrix[i][0] = 0;
        }
    }
};