矩阵置零题目链接https://leetcode.cn/problems/set-matrix-zeroes/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public void setZeroes(int[][] matrix) { int mmatrix.length, nmatrix[0].length; SetInteger line new HashSet(m); SetInteger column new HashSet(n); for(int i0; im; i){ for(int j0; jn; j){ if(matrix[i][j]0){ line.add(i); column.add(j); } } } for(int i:line){ for(int j0; jn; j){ matrix[i][j]0; } } for(int j:column){ for(int i0; im; i){ matrix[i][j]0; } } }分析代码的时间复杂度为O(m*n)空间复杂度为O(mn)。思路是用Set分开收集所有等于0的行下标和列下标最后根据行下标和列下标统一置0。看了官方题解后的解答//官方的方法一与我的大致相同只是将用Set存储下标改为了用boolean数组标记下标 //时间复杂度O(m*n) //空间复杂度O(mn) public void setZeroes(int[][] matrix) { int m matrix.length, n matrix[0].length; boolean[] row new boolean[m]; boolean[] col new boolean[n]; for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 0) { row[i] col[j] true; } } } for (int i 0; i m; i) { for (int j 0; j n; j) { if (row[i] || col[j]) { matrix[i][j] 0; } } } } //方法二使用两个标记变量 //时间复杂度O(m*n) //空间复杂度O(1) //利用两个变量标记第一行和第一列是否需要置0然后用第一行和第一列标记需要置为0的行和列降低空间复杂度 public void setZeroes(int[][] matrix) { int mmatrix.length, nmatrix[0].length; boolean flagRow0 false;//标记第一行是否存在0 boolean flagCol0 false;//标记第一列是否存在0 for(int i0; im; i){ if(matrix[i][0]0){ flagCol0true; break; } } for(int j0; jn; j){ if(matrix[0][j]0){ flagRow0true; break; } } //用数组第一行和第一列标记需要置为0的行和列 for(int i1; im; i){ for(int j1; jn; j){ if(matrix[i][j]0){ matrix[i][0] matrix[0][j] 0; } } } for(int i1; im; i){ for(int j1; jn; j){ if(matrix[i][0]0||matrix[0][j]0){ matrix[i][j]0; } } } //处理第一行 if(flagRow0){ for(int j0; jn; j){ matrix[0][j]0; } } //处理第一列 if(flagCol0){ for(int i0; im; i){ matrix[i][0]0; } } } //方法三使用一个标记变量 //时间复杂度O(m*n) //空间复杂度O(1) //主要思想与方法二一致用数组的第一行和第一列标记需要置为0的行和列 //在方法二的基础上进行优化利用一个变量标记第一列是否需要置0这样数组第一个元素就可以标记第一行是否需要置0 //为了防止第一行的元素被提前更新需要倒序处理数组 public void setZeroes(int[][] matrix) { int m matrix.length, n matrix[0].length; boolean flagCol0 false; for (int i 0; i m; i) { if (matrix[i][0] 0) { flagCol0 true; break; } } for (int i 0; i m; i) { for (int j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] matrix[0][j] 0; } } } for (int i m-1; i 0; i--) { for (int j 1; j n; j) { if (matrix[i][0] 0 || matrix[0][j] 0) { matrix[i][j] 0; } } } if (flagCol0) { for (int i 0; i m; i) { matrix[i][0] 0; } } }分析​ 1、本题的主要思考如何降低空间复杂度。​ 2、方法二和方法三都是利用了变量去单独标记第一行或第一列是否需要置0然后用第一行和第一列标记需要置0的行和列。​ 3、方法三与方法二的区别在于方法三只用了一个变量标记第一列是否需要置0这样位置(0,0)的元素就可以标记第一行是否需要置0但是为了避免第一行提前被更新所以倒序地处理数组。总结本题优化的点主要在于思考如何在O(1)的空间复杂度下对需要处理的行和列做标记。