首页 > 代码库 > LeetCode 73. Set Matrix Zeros(矩阵赋零)
LeetCode 73. Set Matrix Zeros(矩阵赋零)
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
题目标签:Array
Did you use extra space?
A straight forward solution using O(mn) 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?
题目标签:Array
这道题目给了我们一个矩阵,让我们把所有是0的位置的那一行和那一列都改成0。我们自己改成0的位置就不需要再改0了。题目还要求我们用 O(1) space,所以就不能另外新建matrix来辅助了。这道题目的难点在于,如果遇到一个0,把它的那一行和那一列都改成0的话,对之后的遍历其他位置的判断就造成了影响。我们可以把这 (遇到0就改这一行和这一列)步骤分解成4个步骤。利用第一行和第一列来存信息,根据信息来对剩下的所有位置改0。那么我们首先要把第一行和第一列里有没有0的这个信息保存起来。
Step 1: 遍历第一行和第一列,设置两个boolean 来保存,如果有0就是true;
Step 2: 遍历剩下的行和列,如果遇到0,就把对应在第一行和第一列里的相对位置改成0;
Step 3: 和step 2一样,遍历除了第一行和第一列的所有位置,对于每一个位置,如果第一行和第一列里的相对位置是0的话,把这个位置改成0;
Step 4: 最后把第一行和第一列也改0,根据开始存的两个boolean 值。
Java Solution:
Runtime beats 23.97%
完成日期:07/23/2017
关键词:Array
关键点:把原题给的十字改0的这一个过程分解成四个步骤来实现
1 public class Solution 2 { 3 public void setZeroes(int[][] matrix) 4 { 5 boolean firstRow = false; 6 boolean firstCol = false; 7 8 // iterate the first row and column to see any zeros there 9 for(int y=0; y<matrix[0].length; y++) 10 { 11 if(matrix[0][y] == 0) 12 { 13 firstRow = true; 14 break; 15 } 16 } 17 18 for(int x=0; x<matrix.length; x++) 19 { 20 if(matrix[x][0] == 0) 21 { 22 firstCol = true; 23 break; 24 } 25 } 26 27 // iterate rest rows and columns, 28 //if see any zero, put zero in corresponding position in first row and first column 29 for(int x=1; x<matrix.length; x++) // rows 30 { 31 for(int y=1; y<matrix[0].length; y++) // columns 32 { 33 if(matrix[x][y] == 0) 34 { 35 matrix[x][0] = 0; 36 matrix[0][y] = 0; 37 } 38 } 39 } 40 41 // iterate rest rows and columns again, 42 // for each position, if corresponding first row or first column has 0, change this to 0 43 for(int x=1; x<matrix.length; x++) 44 { 45 for(int y=1; y<matrix[0].length; y++) 46 { 47 if(matrix[x][0] == 0 || matrix[0][y] == 0) 48 matrix[x][y] = 0; 49 } 50 } 51 52 53 // check two boolean firstRow and firstCol, and decide need to make first row and first column to 0 54 if(firstRow) 55 for(int y=0; y<matrix[0].length; y++) 56 matrix[0][y] = 0; 57 58 if(firstCol) 59 for(int x=0; x<matrix.length; x++) 60 matrix[x][0] = 0; 61 } 62 }
参考资料:
http://www.cnblogs.com/grandyang/p/4341590.html
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
LeetCode 73. Set Matrix Zeros(矩阵赋零)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。