【矩阵】【中等】矩阵置零

题目给定一个 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]]提示m matrix.lengthn matrix[0].length1 m, n 200-2^31 matrix[i][j] 2^31 - 1进阶一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗方法一复制矩阵复制一样大小和内容的矩阵copy[m][n]如果copy[i][j] 0那么就把原矩阵中的第i行、第j列置零此时的额外空间是O(mn)注意不能直接一边扫描、一边把原矩阵改成 0例如矩阵[1,1,1],[1,0,1],[1,1,1]扫描到中间的时候将行和列都设置为 0变为下面的矩阵[1,0,1],[0,0,0],[1,0,1]这是时候后续扫描到第三行第二列的时候数值也为 0但是它是刚才置零产生不是原有的 0publicstaticvoidsetZeroes(int[][]matrix){//int[][] copy matrix.clone();浅拷贝修改 matrix 会影响 copyint[][]copynewint[matrix.length][matrix[0].length];for(inti0;imatrix.length;i){copy[i]matrix[i].clone();// 或者 Arrays.copyOf(matrix[i], matrix[i].length)}for(inti0;imatrix.length;i){for(intj0;jmatrix[i].length;j){if(copy[i][j]0){//将第i行和第j列设置为0for(intk0;kmatrix.length;k){matrix[k][j]0;}for(intk0;kmatrix[i].length;k){matrix[i][k]0;}}}}}时间复杂度O(mn(mn))空间复杂度O(mn)方法二记录行和列的清零位置根本没必要保存完整矩阵。因为对于每个 0真正需要记住的信息只有第几行要清零和第几列要清零第一遍扫描记录需要清零的行 rows[] 和列 cols[]第二遍扫描如果属于标记的行/列则清零publicstaticvoidsetZeroes(int[][]matrix){boolean[]rownewboolean[matrix.length];boolean[]colnewboolean[matrix[0].length];for(inti0;imatrix.length;i){for(intj0;jmatrix[0].length;j){if(matrix[i][j]0){row[i]true;col[j]true;}}}for(inti0;imatrix.length;i){for(intj0;jmatrix[0].length;j){if(row[i]||col[j]){matrix[i][j]0;}}}}时间复杂度O(mn)空间复杂度O(mn)方法三第一行和第一列充当标记数组矩阵本身已经有第一行和第一列因此可以替代上面的标记位置。注意需要首先记录原始的第一行第一列中是否有0比如对于下面的矩阵检测到 arr[0][1] 处为0则设置matrix[i][0] 0、 matrix[0][j] 0会污染原来的行列因此第一行第一列只能记录内层是否为0原有的0则需要处理完最后再单独处理[1,0,3][4,5,6][7,8,9]publicstaticvoidsetZeroesO1(int[][]matrix){booleanfirstRowZerofalse;booleanfirstColZerofalse;//需要首先记录原始的第一行第一列中是否有0for(inti0;imatrix.length;i){if(matrix[i][0]0){firstColZerotrue;}}for(intj0;jmatrix[0].length;j){if(matrix[0][j]0){firstRowZerotrue;}}//内部0的处理for(inti1;imatrix.length;i){for(intj1;jmatrix[i].length;j){if(matrix[i][j]0){matrix[i][0]0;matrix[0][j]0;}}}for(inti1;imatrix.length;i){for(intj1;jmatrix[i].length;j){if(matrix[i][0]0||matrix[0][j]0){matrix[i][j]0;}}}//对第一行和第一列进行处理if(firstRowZero){for(intj0;jmatrix[0].length;j){matrix[0][j]0;}}if(firstColZero){for(inti0;imatrix.length;i){matrix[i][0]0;}}}时间复杂度O(mn)空间复杂度O(1)