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