将矩阵中值为0的元素所在的行和列设置为0,, in-place O(1)space O(mn) time
分类:算法Java
Given amxnmatrix, 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?
public class Solution {public void setZeroes(int[][] matrix) {int m=matrix.length;if(m==0)return;int n=matrix[0].length;if(n==0)return;boolean preZeros=false;boolean curZeros=false;for(int i=0;i<m;i++){//test if this row has zeros.for(int j=0;j<n;j++){if(matrix[i][j]==0){for(int k=0;k<i;k++)matrix[k][j]=0;curZeros=true;}}//fill the zeros along coloum.if(i>0){for(int j=0;j<n;j++){if(matrix[i-1][j]==0){matrix[i][j]=0;}}}//if pre row has zeros, fill zeros with that row.if(preZeros){for(int j=0;j<n;j++){matrix[i-1][j]=0;}}preZeros=curZeros;curZeros=false;}if(preZeros){for(int j=0;j<n;j++){matrix[m-1][j]=0;}}}}
上一篇二叉树最近公共祖先问题(O(n) time 且只遍历一遍,O(1) Space (不考虑函数调用栈的空间))
顶1踩0
当你能飞的时候就不要放弃飞