leetcode Top100(17)矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

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

示例 2：

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

package TOP11_20;import java.util.HashSet;
import java.util.Set;//  矩阵置零
//给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
// 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
//输出：[[1,0,1],[0,0,0],[1,0,1]]
public class Top18 {// 用两个hash表记录行和列为0的数据 然后再修改数组值public static void setZeroes(int[][] matrix) {Set colZeroSets = new HashSet();Set rowZeroSets = new HashSet();int row = matrix.length;int height = matrix[0].length;for (int i = 0; i < row; i++) {for (int j = 0; j < height; j++) {if (matrix[i][j] == 0) {colZeroSets.add(i);rowZeroSets.add(j);}}}for (int i = 0; i < row; i++) {for (int j = 0; j < height; j++) {if (colZeroSets.contains(i) || rowZeroSets.contains(j)) {matrix[i][i] = 0;}}}}// 直接用第一行和第一列 来记录，但先将第一行和第一列是否有为0的数据记录下来 然后再赋值，最后赋值第一行和第一列public static void setZeroes2(int[][] matrix) {int row = matrix.length;int height = matrix[0].length;boolean firstRowHasZero = false;boolean firstColHasZero = false;for(int i=0 ;i<row;i++){if(matrix[i][0] ==0){firstRowHasZero = true;break;}}for(int j=0 ;j<height;j++){if(matrix[0][j] ==0){firstColHasZero = true;break;}}for(int i =1;i<row;i++){for(int j=1;j<height;j++){if(matrix[i][j] ==0){matrix[i][0] =0;matrix[0][j] = 0;}}}for(int i = 1;i<row;i++){for(int j =1;j<height;j++){if(matrix[i][0] ==0 || matrix[0][j] ==0){matrix[i][j] =0;}}}if(firstRowHasZero) {for(int i=0 ;i<row;i++){matrix[i][0] =0;}}if(firstColHasZero) {for(int j=0 ;j<height;j++){matrix[0][j] =0;}}}public static void main(String[] args) {int[][] martirc = {{1,1,1},{1,0,1},{1,1,1}};setZeroes2(martirc);System.out.println("end");}
}

harryptter / LeetcodeTop100 · GitCode