51网站空间相册_广告设计与制作专业学什么课程_中国搜索引擎大全_seo外包服务项目

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

C++

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int rows=matrix.size();int cols=matrix[0].size();int first_row=0;int first_col=0;for( int i=0;i<rows;i++ ){if( !matrix[i][0] ){first_col=1;}}for( int i=0;i<cols;i++ ){if( !matrix[0][i] ){first_row=1;}}for( int i=1;i<rows;i++ ){for( int j=1;j<cols;j++ ){if( !matrix[i][j] ){matrix[i][0]=matrix[0][j]=0;}}}for( int i=1;i<rows;i++ ){for( int j=1;j<cols;j++ ){if( !matrix[i][0] || !matrix[0][j] ){matrix[i][j]=0;}}}if( first_col ){for( int i=0;i<rows;i++ ){matrix[i][0]=0;}}if( first_row ){for( int i=0;i<cols;i++ ){matrix[0][i]=0;}}}
};

时间复杂度

$O(M\ast N)$

空间复杂度

$O(M+N)$

Java

class Solution {public void setZeroes(int[][] matrix) {int rows=matrix.length;int cols=matrix[0].length;int first_row=0;int first_col=0;for( int i=0;i<rows;i++ ){if( 0==matrix[i][0] ){first_col=1;}}for( int i=0;i<cols;i++ ){if(0==matrix[0][i]){first_row=1;}}for( int i=1;i<rows;i++ ){for( int j=1;j<cols;j++ ){if( 0==matrix[i][j] ){matrix[i][0]=matrix[0][j]=0;}}}for( int i=1;i<rows;i++ ){for( int j=1;j<cols;j++ ){if( 0==matrix[i][0] || 0==matrix[0][j] ){matrix[i][j]=0;}}}if( 1==first_col ){for( int i=0;i<rows;i++ ){matrix[i][0]=0;}}if( 1==first_row ){for( int i=0;i<cols;i++ ){matrix[0][i]=0;}}}
}

时间复杂度

$O(M\ast N)$

空间复杂度

$O(M+N)$

Python

class Solution:def setZeroes(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""rows=len(matrix);cols=len(matrix[0]);first_row=False;first_col=False;for i in range(rows):if not matrix[i][0]:first_col=True;for i in range(cols):if not matrix[0][i]:first_row=True;for i in range(1,rows):for j in range(1,cols):if not matrix[i][j]:matrix[i][0]=matrix[0][j]=0;for i in range(1,rows):for j in range(1,cols):if not matrix[i][0] or not matrix[0][j]:matrix[i][j]=0;if first_col:for i in range(rows):matrix[i][0]=0;if first_row:for i in range(cols):matrix[0][i]=0;

时间复杂度

$O(M\ast N)$

空间复杂度

$O(M+N)$