首页 > 代码库 > 【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.
题解:因为题目要求原地算法,所以我们只能利用矩阵第一行和第一列存放置零信息。
- 首先遍历第一行和第一列,看他们是否需要全部置零,用两个变量first_column_zero和first_row_zero来记录;
- 遍历矩阵,如果某个位置matrix[i][j]出现了0,就把matrix[i][0]和Matrix[0][j]置零;这一步虽然改变了第一行第一列的元素,但是是正确的,因为这一行对应的位置因为Matrix[i][j]处的0最后的确是要变成0的;
- 遍历矩阵,如果(i,j)处对应的(i,0)或者(0,j)处为0,那么这个元素就置零;
- 单独处理第一行第一列,根据第一步的变量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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。