首页 > 代码库 > 【leetcode刷题笔记】Set Matrix Zeroes

【leetcode刷题笔记】Set Matrix Zeroes

2024-07-11 00:51:14   216人阅读

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

 

题解：因为题目要求原地算法，所以我们只能利用矩阵第一行和第一列存放置零信息。

  1. 首先遍历第一行和第一列，看他们是否需要全部置零，用两个变量first_column_zero和first_row_zero来记录；
  2. 遍历矩阵，如果某个位置matrix[i][j]出现了0，就把matrix[i][0]和Matrix[0][j]置零；这一步虽然改变了第一行第一列的元素，但是是正确的，因为这一行对应的位置因为Matrix[i][j]处的0最后的确是要变成0的；
  3. 遍历矩阵，如果(i,j)处对应的(i,0)或者(0,j)处为0，那么这个元素就置零；
  4. 单独处理第一行第一列，根据第一步的变量first_column_zero和first_row_zero。

代码如下：

 1 public class Solution { 2     public void setZeroes(int[][] matrix) { 3         int m = matrix.length; 4         int n = matrix[0].length; 5         boolean first_column_zero = false; 6         boolean first_row_zero = false; 7          8         for(int i = 0;i < m;i ++){ 9             if(matrix[i][0] == 0)10                 first_column_zero =true;11         }12         for(int i = 0;i < n;i ++){13             if(matrix[0][i] == 0)14                 first_row_zero = true;15         }16         17         for(int i = 1;i < m;i++){18             for(int j = 1;j < n;j ++){19                 if(matrix[i][j]== 0){20                     matrix[i][0] = 0;21                     matrix[0][j]= 0; 22                 }23             }24         }25         26         for(int i = 1;i < m;i++){27             for(int j = 1;j < n;j ++){28                 if(matrix[i][0] == 0 || matrix[0][j]== 0 )29                     matrix[i][j]= 0; 30             }31         }32         33         if(first_column_zero){34             for(int i = 0;i < m;i ++)35                 matrix[i][0] = 0;36         }37         if(first_row_zero){38             for(int i = 0;i < n;i ++)39                 matrix[0][i] = 0;40         }41     }42 }

 


联系
我们