73. 矩阵置零
题目描述
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例:
输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ]
暴力求解思路
1.遍历数组中的每个元素,若这个元素等于0,则分别使用两个Set记录下这个元素的横坐标和纵坐标。
2.遍历两个Set,将其中的行和列的值都置成0。
3.由于题目要求的是原地法,我们使用了额外空间,所以不符合要求。
Java代码实现
public void setZeroes(int[][] matrix) { Set<Integer> rows = new HashSet<>(); Set<Integer> cols = new HashSet<>(); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if(matrix[i][j] == 0){ rows.add(i); cols.add(j); } } } for (Integer row:rows) { for (int i = 0; i < matrix[0].length; i++) { matrix[row][i] = 0; } } for (Integer col:cols) { for (int i = 0; i < matrix.length; i++) { matrix[i][col] = 0; } } }
原地法修改思路
1.我们可以使用该二维数组的第一行和第一列达到和暴力法种两个Set相同的效果。
2.为了防止第一行和第一列标识相互影响,我们应该从第一行第二列或者第二行第一列遍历整个数组,若遍历到的元素等于0,则将此行和此列的第一个元素置为0。
3.由于第一行和第一列是标识位,所以我们二次遍历数组时,应该从第二行第二列开始遍历,若该元素所在行或列的第一个元素等于0,我们就将该元素置为0。
4.最后特殊处理第一行和第一列即可。
Java代码实现
public void setZeroes(int[][] matrix) { boolean colFlag = false; for (int i = 0; i < matrix.length; i++) { //第一列需要被置0 if(matrix[i][0] == 0) colFlag = true; for (int j = 1; j < matrix[0].length; j++) { if(matrix[i][j] == 0){ //该元素所在的行和列标记为需要被置0 matrix[i][0] = 0; matrix[0][j] = 0; } } } //将被标记的行和列的元素置0 for (int i = 1; i < matrix.length; i++) { for (int j = 1; j < matrix[0].length; j++) { if(matrix[i][0] == 0 || matrix[0][j] == 0){ matrix[i][j] = 0; } } } //判断第一行是否要被置0 if(matrix[0][0] == 0){ for (int i = 0; i < matrix[0].length; i++) { matrix[0][i] = 0; } } //判断第一列是否要被置0 if(colFlag){ for (int i = 0; i < matrix.length; i++) { matrix[i][0] = 0; } } }