网站seo优化服务_科技厅_网站外链购买_seo关键词挖掘工具

Problem: 73. 矩阵置零

思路

循环遍历数组

解题过程

第一次遍历，找到矩阵中0出现的位置，将所在行，列进行标志 第二次开始置0，如果某个元素的行，列之一之前被标记了，那么将这个元素置0（先找到行，列然后将所在行，列的元素逐个置0）

问题

为什么需要设置布尔类型的数组？

布尔类型的值只有两种：true，false，大大节省空间和时间效率

为什么需要设置两个布尔数组，不是已经有i,j代表行，列吗？

在遍历数组时，可以不要数组来代表行列，但是在置0时，需要找到元素所在的行，列，如果单纯的将出现0，马上置0，会影响结果，因为某些0可能不是矩阵中的，而是被置0后的结果

在第一次遍历矩阵的过程中，我们发现某些元素是0，并因此知道这些元素所在的行和列最终需要被置为0。但是，如果我们在发现一个0的时候立即把整行或整列置为0，这会影响后续的检查（即，可能会错误地标记其他不应该被置为0的行或列）。因此，我们需要一种方法来记住所有的这些行和列的信息，以便在完成整个矩阵的遍历之后再进行处理。

复杂度

• 时间复杂度: O(m+n)

Code

class Solution {public void setZeroes(int[][] matrix) {boolean[] row=new boolean[matrix.length];boolean[] col=new boolean[matrix[0].length];//第一次遍历，确定哪些行和列需要置0for(int i=0;i<matrix.length;i++){for(int j=0;j<matrix[i].length;j++){if(matrix[i][j]==0){row[i]=true;col[j]=true;}}}//开始置0：for(int i=0;i<matrix.length;i++){for(int j=0;j<matrix[i].length;j++){if(row[i]||col[j]){matrix[i][j]=0;}}}}}