Cracking Coding Interview - 1.8 Zero Matrix

Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

分析

看似是遍历整个二维数组,如果发现某个点为0,那么就把X轴和Y轴都清零。

题目里没有讲清楚两个事情:

  1. 这个matrix里究竟有几个0
  2. 因为遇到第一个0之后把X轴和Y轴都清零了,那么如果继续查找肯定会把整个matrix都清0,这种情况怎么处理

假设这两个问题的答案是:

  1. 有任意多个0
  2. 对清零过的cell跳过,不做处理

解答

从左到右从上到下遍历整个matrix。

记录那些行,哪些列有0,其实就是坐标,然后遍历这些,把行列清零。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public void zeroMatrix(int[][] matrix, int m, int n) {
  // m: 行数, n: 列数
  boolean[] zeroRows = new boolean[m]
  boolean[] zeroCols = new boolean[n];
  for(int i = 0; i < m; i++) {
    for(int j = 0; j < n; j++) {
      if (matrix[i][j] == 0) {
        zeroRows[i] = true;
        zeroCols[j] = true;
      }
    }
  }
  for(int i = 0; i < m; i++) {
    if (zeroRows[i]) {
      zeroRows(matrix[i]);
    }
  }
  for(int i = 0; i < n; i++) {
    if (zeroCols[i]) {
      zeroCols(matrix, i);
    }
  }
}
private void zeroRow(int[] array) {
  for(int i = 0; i < array.length; i++) {
    array[i] = 0;
  }
}
private void zeroCol(int[][] matrix, int col) {
  for(int i = 0; i < matrix.length; i++) {
    matrix[i][col] = 0;
  }
}

时间复杂度:O(n*m)

空间复杂度:O(n+m)

版权

评论