面试题7 指定一个m*n的整数矩阵如果(r, c)位置元素的元素是0 则将行 r 和列 c 整个变成0

面试题7 指定一个m*n的整数矩阵如果(r, c)位置元素的元素是0 则将行 r 和列 c 整个变成0 - 雄霸天下-无人能挡

文章转载自:http://www.pythonheidong.com/blog/article/2857/

题目: 指定一个 m*n 的整数数组如果其中一个元素是0 则将该行和该列都变成0

思路: 看起来是很简单的一道题但是问题是我们不能一边查找一边将行和列变成0, 因为如果这样了只要有一个 0 后面的所有位置都会被设置成0 所有后面的所有行列也都变成了0 但是如果他们原本不是 0 我们的算法就出错了

所以思路就是先确认哪些行和列需要归0 然后在将他们归0 代码如下

  public void mySolution(int[][] matrix){
    if(!isValidMatrix(matrix))  return;

    int numOfRows = matrix.length;
    int numOfCols = matrix[0].length;

    boolean[] rows = new boolean[numOfRows];
    boolean[] cols = new boolean[numOfCols];

    for(int i=0; i<numOfRows; i++){
      for(int j=0; j<numOfCols; j++){
        if(matrix[i][j]==0){
          rows[i] = true;
          cols[j] = true;
        }
      }
    }

    for(int i=0; i<rows.length; i++)
      if(rows[i])
        for(int j=0; j<numOfCols; j++)  matrix[i][j] = 0;

    for(int i=0; i<cols.length; i++)
      if(cols[i])
        for(int j=0; j<numOfRows; j++)  matrix[j][i] = 0;
  }

  private boolean isValidMatrix(int[][] a){
    if(a==null) return false;
    if(a.length==0) return false;
    if(a[0]==null)  return false;
    if(a[0].length==0)  return false;
    return true;
  }

该方法的时间复杂度是 O(m*n) 空间复杂度是 O(m+n) 因为我们要2个数组追踪哪些行和列需要归0

下面的方法将空间复杂度降低到 O(1) 思路和前面的方法是一样的但是它巧妙地运用了原数组的第一行和第一列来储存需要将哪些行和列归0, 所以降低了空间复杂度代码如下

  public void goodSolution(int[][] matrix){
    if(!isValidMatrix(matrix))  return;

    int numOfRows = matrix.length;
    int numOfCols = matrix[0].length;

    boolean firstRowHasZero = false;
    boolean firstColHasZero = false;

    for(int i=0; i<numOfCols; i++){
      if(matrix[0][i]==0){
        firstRowHasZero = true;
        break;
      }
    }
    for(int i=0; i<numOfRows; i++){
      if(matrix[i][0]==0){
        firstColHasZero = true;
        break;
      }
    }

    for(int i=1; i<numOfRows; i++){
      for(int j=1; j<numOfCols; j++){
        if(matrix[i][j]==0){
          matrix[i][0] = 0;
          matrix[0][j] = 0;
        }
      }
    }

    for(int i=1; i<numOfRows; i++)
      if(matrix[i][0]==0)
        nullifyRow(matrix, i);
    for(int i=1; i<numOfCols; i++)
      if(matrix[0][i]==0)
        nullifyCol(matrix, i);

    if(firstRowHasZero) nullifyRow(matrix, 0);
    if(firstColHasZero) nullifyCol(matrix, 0);
  }


  private void nullifyRow(int[][] a, int row){
    for(int i=0; i<a[0].length; i++)
      a[row][i] = 0;
  }
  
  private void nullifyCol(int[][] a, int col){
    for(int i=0; i<a.length; i++)
      a[i][col] = 0;
  }

该方法的时间复杂度依然是O(m*n) 但是空间复杂度提升到了 O(1) 是目前最优解

文章转载自:http://www.pythonheidong.com/blog/article/2857/

原文链接：http://www.cnblogs.com/xiongbatianxiaskjdskjdksjdskdtuti/p/11350061.html