LeetCode：矩阵置零

方法一O(MN)class Solution { public void setZeroes(int[][] matrix) { int m matrix.length; int n matrix[0].length; //申请一个和原矩阵完全等大的新矩阵 int[][] copy new int[m][n]; //把旧矩阵的数据原封不动地搬过来 for (int i 0; i m; i) { for (int j 0; j n; j) { copy[i][j] matrix[i][j]; } } //看着原矩阵 (copy) 找 0在真实矩阵 (matrix)处理 for (int i 0; i m; i) { for (int j 0; j n; j) { if (copy[i][j] 0) { for (int k 0; k n; k) { matrix[i][k] 0; } for (int k 0; k m; k) { matrix[k][j] 0; } } } } } }方法二O(MN)class Solution { public void setZeroes(int[][] matrix) { int m matrix.length; int n matrix[0].length; //记录每一行和每一列的状态 //boolean数组默认全是false boolean[] rowDeathList new boolean[m]; boolean[] colDeathList new boolean[n]; //全矩阵扫描填写状态 for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 0) { rowDeathList[i] true; colDeathList[j] true; } } } //根据状态给矩阵置0 for (int i 0; i m; i) { for (int j 0; j n; j) { if (rowDeathList[i] || colDeathList[j]) { matrix[i][j] 0; } } } } }方法三O(1)class Solution { public void setZeroes(int[][] matrix) { int m matrix.length; int n matrix[0].length; //只用于处理第一列设置的变量 boolean firstColHasZero false; //遍历在第一行和第一列置0设置状态 for(int i 0; i m; i){ if(matrix[i][0] 0){ firstColHasZero true; } for(int j 1; j n; j){ if(matrix[i][j] 0){ matrix[i][0] 0; matrix[0][j] 0; } } } //遍历将需要的行和列置0 for(int i 1; i m; i){ for(int j 1; j n; j){ if(matrix[i][0] 0 || matrix[0][j] 0){ matrix[i][j] 0; } } } //处理第一行第一列 if(matrix[0][0] 0){ for(int j 0; j n; j){ matrix[0][j] 0; } } if(firstColHasZero){ for(int i 0; i m; i){ matrix[i][0] 0; } } } }1.空间复杂度为O(MN)方法开辟新的矩阵2.空间复杂度为O(MN)方法两个一维数组用于行记录和列记录3.空间复杂度O(1)将原数组的某部分当作状态数组步骤1第一行/第一列专门记录哪行/列设为0因为[0][0]既属于第一行又属于第一列我们让它只管第一行然后再引入一个变量firstColHasZero专门负责第一列先扫第一列只要有0直接将firstColHasZero置为true因为第一列已经清楚了所以直接从j1开始往后扫扫描中只要[i][j]为0将[i][0],[0][j]置为0现在就统计好应该设为0的行和列了2根据将刚才第一行第一列的状态开始将矩阵符合条件的行列置为0防止一上来将第一行第一列元素置为0导致后面元素误设为0所以从ij为1的位置开始3最后处理第一行和第一列[0][0]如果是0将第一行置为0firstColHasZero如果是true这一列直接置为0