首页 > 代码库 > [leetcode]Set Matrix Zeroes
[leetcode]Set Matrix Zeroes
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.
Follow up:
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?
这道题前天实验室同学问过我，今天简单整理一下四种空间复杂度的解法，时间复杂度肯定是一样的O(mn)
算法：
思路1. 空间复杂度O(mn)
开辟O(m*n)空间tag，标记matrix中每个0的位置，全部标记完之后，再遍历tag，将matrix相关行列赋0
1 public class Solution { 2 public void setZeroes(int[][] matrix) { 3 if(matrix == null || matrix.length == 0) return; 4 int height = matrix.length; 5 int width = matrix[0].length; 6 boolean[][] tag = new boolean[height][width]; 7 for(int i = 0; i < height; i++){ 8 for(int j = 0; j < width; j++){ 9 if(matrix[i][j] == 0)10 tag[i][j] = true;11 }12 }13 for(int i = 0; i < height; i++){14 for(int j = 0; j < width; j++){15 if(tag[i][j]){16 setZero(matrix, height, width, i, j);17 }18 }19 }20 }21 private void setZero(int[][] matrix,int height,int width,int row,int column){22 for(int i = 0; i < height; matrix[i++][column] = 0);23 for(int i = 0; i < width; matrix[row][i++] = 0);24 }25 }
思路2. 空间复杂度O(m+n)
因为题中要求某行只要有0，即将该行全部置0，因此，我们无须关心该行的0出现在哪一列。同理，列一样一样处理。
1 public class Solution { 2 public void setZeroes(int[][] matrix) { 3 if(matrix == null || matrix.length == 0) return; 4 int height = matrix.length; 5 int width = matrix[0].length; 6 Set<Integer> rowSet = new HashSet<Integer>(); 7 Set<Integer> columnSet = new HashSet<Integer>(); 8 for(int i = 0; i < height; i++){ 9 for(int j = 0; j < width; j++){10 if(matrix[i][j] == 0){11 rowSet.add(i);12 columnSet.add(j);13 }14 }15 }16 for(int row : rowSet){17 for(int i = 0; i < width; matrix[row][i++] = 0);18 }19 for(int column : columnSet){20 for(int i = 0; i < height; matrix[i++][column] = 0);21 }22 }23 }
思路3. 空间复杂度O(m)或者O(n)
在扫描每一行的时候，用一个Boolean值标记该行是否含0，（如果含有0）并将0的列号记录下来（columnSet），该行扫描结束时，将该行全部置0，matrix扫描完之后进行列的统一处理。
1 public class Solution { 2 public void setZeroes(int[][] matrix) { 3 if(matrix == null || matrix.length == 0) return; 4 int height = matrix.length; 5 int width = matrix[0].length; 6 boolean hasZero = false; 7 Set<Integer> columnSet = new HashSet<Integer>(); 8 for(int i = 0; i < height; i++){ 9 hasZero = false;10 for(int j = 0; j < width; j++){11 if(matrix[i][j] == 0){12 hasZero = true;13 columnSet.add(j);14 }15 }16 if(hasZero) 17 for(int j = 0; j < width; matrix[i][j++] = 0);18 }19 for(int column : columnSet){20 for(int i = 0; i < height; matrix[i++][column] = 0);21 }22 }23 }
思路4. 空间复杂度O(1)
这个思路是在思路3的基础上做了优化，将本应记录在columnSet的列号，记录在第1行中的相应列（其他行也可以，但是稍有区别，大家可以想一下）
1 public class Solution { 2 public void setZeroes(int[][] matrix) { 3 if(matrix == null || matrix.length == 0) return; 4 int height = matrix.length; 5 int width = matrix[0].length; 6 boolean hasZeroInFirstRow = false; 7 for(int j = 0; j < width; j++){ 8 if(matrix[0][j] == 0) 9 hasZeroInFirstRow = true;10 }11 for(int i = 1; i < height; i++){12 boolean hasZero = false;13 for(int j = 0; j < width; j++){14 if(matrix[i][j] == 0){15 hasZero = true;16 matrix[0][j] = 0;17 }18 }19 if(hasZero)20 for(int j = 0; j < width; matrix[i][j++] = 0);21 }22 for(int j = 0; j < width; j++){23 if(matrix[0][j] == 0){24 for(int i = 0; i < height; matrix[i++][j] = 0);25 }26 }27 if(hasZeroInFirstRow)28 for(int j = 0; j < width; matrix[0][j++] = 0);29 }30 }
以上四种算法的时间复杂度都是O(m*n)，空间复杂度从O(m*n)到O(1)，可能代码写的不够简洁，但是可读性应该还好吧，哈哈。FYI