73. 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?

代码:

题目很简单,就是矩阵中如果存在值为0的元素,就把该元素对应的行和列上面的元素全都改成0。

思考了半天,还是遍历了两遍,复杂度至少在O(mn):

public void setZeroes(int[][] matrix) {
         int i,j;
         ArrayList<Integer> row = new ArrayList<Integer>();
         ArrayList<Integer> col = new ArrayList<Integer>();        
         //第一个循环,遍历一遍,记录哪些行和哪些列需要改成0
         for (i=0;i < matrix.length;i++)
         { 
          for (j=0;j<matrix[i].length;j++)
          {
           if(matrix[i][j] == 0)
           {
            row.add(i);
            col.add(j);
           }
          }       
         }
       //第二个循环,又遍历一遍,根据需要变为0的行和列修改对应元素
         for (i=0;i < matrix.length;i++)
         { 
          for (j=0;j<matrix[i].length;j++)
          {
           if(row.contains(i)||col.contains(j))
           {
            matrix[i][j] =0;
//            System.out.print("修改第"+i+"行,第"+j+"列");
           } 
          }       
         }
 
     }

题目中提到算法复杂度可以小于 O(m + n),还在研究中...

上一篇:【吐血整理】svn命令行,Subversion的正确使用姿势~


下一篇:【转】USB协议架构及驱动架构