矩阵-73. 矩阵置零

文章目录一、核心解题思路二、完整可运行代码大厂机考版力扣地址 中等73. 矩阵置零挺简单的一、核心解题思路这道题要求原地算法不能用额外 O (mn) 或 O (mn) 的辅助数组只能用 O (1) 额外空间核心思路是用矩阵的第一行、第一列作为「标记数组」遍历矩阵若某个位置matrix[i][j] 0就把matrix[0][j]第一行对应列和matrix[i][0]第一列对应行置为 0标记该行列需要置零。单独标记第一行因为第一行本身会被用来做标记所以用一个额外变量zeroRow记录第一行是否原本就有 0避免后续覆盖。根据标记置零从第 2 行、第 2 列开始遍历若对应行首 / 列首为 0则当前位置置 0。处理第一行、第一列最后根据zeroRow处理第一行根据matrix[0][0]处理第一列。classSolution{publicvoidsetZeroes(int[][]matrix){intmmatrix.length;intnmatrix[0].length;intzeroRow1;for(inti0;im;i){for(intj0;jn;j){if(matrix[i][j]0){if(i0){zeroRow0;}else{matrix[i][0]0;}matrix[0][j]0;}}}for(inti1;im;i){for(intj1;jn;j){if(matrix[i][0]0||matrix[0][j]0){matrix[i][j]0;}}}if(matrix[0][0]0){for(inti0;im;i){matrix[i][0]0;}}if(zeroRow0){for(intj0;jn;j){matrix[0][j]0;}}}}二、完整可运行代码大厂机考版importjava.util.Scanner;publicclassMain{publicstaticvoidsetZeroes(int[][]matrix){intmmatrix.length;intnmatrix[0].length;// 标记第一行是否需要置零intzeroRow1;// 第一步遍历矩阵用第一行、第一列做标记for(inti0;im;i){for(intj0;jn;j){if(matrix[i][j]0){// 区分第一行和其他行if(i0){zeroRow0;}else{matrix[i][0]0;}// 标记对应列matrix[0][j]0;}}}// 第二步根据标记从(1,1)开始置零for(inti1;im;i){for(intj1;jn;j){if(matrix[i][0]0||matrix[0][j]0){matrix[i][j]0;}}}// 第三步处理第一列根据matrix[0][0]if(matrix[0][0]0){for(inti0;im;i){matrix[i][0]0;}}// 第四步处理第一行根据zeroRowif(zeroRow0){for(intj0;jn;j){matrix[0][j]0;}}}publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);intmscanner.nextInt();intnscanner.nextInt();int[][]matrixnewint[m][n];for(inti0;im;i){for(intj0;jn;j){matrix[i][j]scanner.nextInt();}}setZeroes(matrix);for(inti0;im;i){for(intj0;jn;j){System.out.print(matrix[i][j] );}System.out.println();}}}