面试题 01.08. 零矩阵

难度中等111收藏分享切换为英文接收动态反馈

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2：

输入：
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出：
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

题解：

简单模拟题，首先定义两个容量为行数和列数得bool数组，然后扫描整个二维数组，找出为0的行列，在bool数组中标记，然后再次扫描整个数组，将行或者列标记为true的数组下标赋值为0；

class Solution {

  public void setZeroes(int[][] mat) {

​    int n = mat.length, m = mat[0].length;

​    boolean[] rows = new boolean[n], cols = new boolean[m];

​    for (int i = 0; i < n; i++) {

​      for (int j = 0; j < m; j++) {

​        if (mat[i][j] == 0) rows[i] = cols[j] = true;

​      }

​    }

​    for (int i = 0; i < n; i++) {

​      for (int j = 0; j < m; j++) {

​        if (rows[i] || cols[j]) mat[i][j] = 0;

​      }

​    }

  }

}