Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ]
Example 2:
Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]
Follow up:
- 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?
A:
Method 1: O(m+n) space, using two linked list to record where the zeros occurredpublic class Solution { public void setZeroes(int[][] matrix) { // Use linked list to record where zeros occurs if(matrix == null || matrix.length ==0) return; int m = matrix.length, n = matrix[0].length; List rowList = new LinkedList<Integer>(); List colList = new LinkedList<Integer>(); for(int i =0;i<m;i++){ for(int j =0;j<n; j++){ if(matrix[i][j] == 0){ rowList.add(i); colList.add(j); } } } // set row to zeros for(int i : rowList)
Arrays.fill(matrix[i],0); for(int j : colList) for(int i =0;i<m;i++) matrix[i][j]=0; } }
-------------------------------------下面的方法,是在网上找的---------------
常数空间的话,第一可以考虑是不是固定数量的几个变量能搞定;否则可以考虑是不是问题本身已经提供了足够的空间。
这道题属于后者,就是利用矩阵的第一行和第一列来作为辅助空间使用。不用开辟新的存储空间。方法就是:
1.. 找到第一个0, 该行和列就可以用来做标记, 用row0, col0 来表示
2.扫描剩下的矩阵元素,如果遇到了0,就将对应的第一行和第一列上的元素赋值为0
这里不用担心会将本来第一行或第一列的1改成了0,因为这些值最后注定要成为0的。
3.根据第一行和第一列的信息,已经可以将剩下的矩阵元素赋值为结果所需的值了
即,拿第一行为例,如果扫描到一个0,就将这一列都清0.
4.根据1中确定的状态,处理第一行和第一列。
如果最开始得到的第一行中有0的话,就整行清零。同理对列进行处理。
class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); // check first row bool firstRow0 = false, firstCol0 = false; for(int j=0;j<n;++j) if(!matrix[0][j]) { firstRow0 = true; break; } for(int i=0;i<m;++i) if(!matrix[i][0]) { firstCol0=true; break; } for(int i=1;i<m;++i) for(int j=1;j<n;++j) if(!matrix[i][j]) matrix[0][j] = matrix[i][0] = 0; // now set all as zero for(int i=1;i<m;++i) // check first column if(!matrix[i][0]) fill(matrix[i].begin()+1, matrix[i].end(), 0); for(int j = 1; j<n;++j) if(!matrix[0][j]) for(int i=1;i<m;++i) matrix[i][j]=0; if(firstRow0) fill(matrix[0].begin(), matrix[0].end(), 0); if(firstCol0) for(int i =0; i<m;++i) matrix[i][0]=0; } };
Mistakes:
1: 对method1, 因为最后的那个 setCol zeros的循环, are copied from above,,though we take GREAT care, we still forget to change the n to m.
2: method 2 中, 方法的刚开始,我们假设当到了squareLen ==1的时候,就是最后右下角的item. 但是,我们忘记了。当只有一行的时候,squareLen 也是1 的。 -------------------导致这个原因, 有一部分原因,是在于开始,我们对square==1的情况,(当是最后一行或者最后一列时) 我们也要递归调用的。 ----------当然,更重要的是,各种情况考虑不完善,
3: for loop中的jj ++ 给写成了j ++ . ╮(╯▽╰)╭~~~~~~~~~~~~~~~~~~~~
Learned:
---------------------第二遍,------ 先找到一个不在matrix中出现过的数,然后,扫描所有的0, 并将全部的行列的非零值 设 为那个数字。 。 最后,再把其改成0.
public class Solution { public void setZeroes(int[][] matrix) { // assume Integer.MIN_VALUE is not used in matrix int m = matrix.length; if (m == 0) return; int n = matrix[0].length; // find special value that does not appear in matrix boolean findNonUsed = false; int specialVal = 0; while (!findNonUsed) { findNonUsed = true; double up = Integer.MAX_VALUE ; double low = Integer.MIN_VALUE; double val = Math.random() * ( up - low) + low ; specialVal = (int) val; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == specialVal) findNonUsed = false; } // change row and column into the special value , for (int i = 0; i < m; i++) { boolean flag = false; // flag whether this row should be set to zero for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { flag = true; // set j_th column as zero for (int k = 0; k < m; k++) if(matrix[k][j] != 0){ matrix[k][j] = specialVal; } } } if (flag) for (int j = 0; j < n; j++) matrix[i][j] = specialVal; } // change all Integer.MIN_VALUE to zero for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == specialVal) matrix[i][j] = 0; } }
------------3rd Pass ---------------还是第一遍的思路,找个行,列,然后在上面改--------------
public class Solution { public void setZeroes(int[][] matrix) { int row0 = -1, col0 = -1; int m = matrix.length, n = matrix[0].length; for(int i =0;i< m;i++){ for(int j =0;j<n;j++){ if(matrix[i][j] != 0) continue; if(row0<0){ row0 = i; col0 = j; } matrix[row0][j] = 0; matrix[i][col0] = 0; } } if(row0<0) // not found 0 at all return; // set all rows for(int i =0;i<m; i++) if(i != row0 && matrix[i][col0]==0) Arrays.fill(matrix[i],0); //set all columns for(int j =0;j<n;j++) if(matrix[row0][j]==0)// set the entire column as 0 for(int i =0;i< m;i++) matrix[i][j] = 0; Arrays.fill(matrix[row0],0); } }
Mistakes:
1:忘记check 是否找到过 0
No comments:
Post a Comment