力扣热门100题之矩阵置零

这道题要求不能用额外空间必须用矩阵第一行、第一列当作标记位是面试高频题核心思路原地算法用第一行、第一列本身记录哪些行、哪些列需要置 0先单独判断第一行、第一列本身是否有 0遍历其他元素遇到 0 就标记到第一行对应列、第一列对应行根据标记把对应行、列置 0最后处理第一行、第一列超级通俗大白话解释1. 为什么要单独标记第一行、第一列因为第一行、第一列要用来当标记位不能先把它们直接置 0否则会丢失原本的标记信息。2. 核心标记规则如果matrix[i][j] 0就让第一行第 j 列 0表示这一列要清零就让第 i 行第一列 0表示这一行要清零3. 最后清零看第一列 → 哪行标 0 → 整行清零看第一行 → 哪列标 0 → 整列清零最后根据一开始记录的firstRow、firstCol清零第一行、第一列完整代码实现class Solution { public void setZeroes(int[][] matrix) { int m matrix.length; // 行数 int n matrix[0].length; //列数 // 标记第一行是否有 0 boolean firstRow false; // 标记第一列是否有 0 boolean firstCol false; // 检查第一行是否有0 for (int j 0; j matrix[0].length; j) { if (matrix[0][j] 0) { firstRow true; break; } } // 检查第一列是否有0 for (int i 0; i matrix.length; i) { if (matrix[i][0] 0) { firstCol true; break; } } // 3. 遍历除第一行、第一列外的元素 // 如果 matrix[i][j] 0就标记到第一行和第一列 for (int i 1; i m; i) { for (int j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] 0; // 标记第 i 行需要置 0 matrix[0][j] 0; // 标记第 j 列需要置 0 } } } // 4. 根据第一列的标记把对应行置为0 for (int i 1; i m; i) { if (matrix[i][0] 0) { for (int j 1; j n; j) { matrix[i][j] 0; } } } // 根据第一行的标记 把对应列置为0 for(int j 1; j n; j){ if(matrix[0][j] 0){ for(int i 1;im;i){ matrix[i][j] 0; } } } //最后处理第一行 if(firstRow){ for(int j 0;jn;j){ matrix[0][j] 0; } } //处理第一列 if(firstCol){ for(int i 0;im;i){ matrix[i][0] 0; } } } }