LeetCode HOT 100 —— 矩阵置零（多种解法详解）

题目描述LeetCode 73. 矩阵置零给定一个m x n的矩阵如果一个元素为0则将其所在行和列的所有元素都设为0。请使用原地算法。示例 1text输入matrix [[1,1,1],[1,0,1],[1,1,1]] 输出[[1,0,1],[0,0,0],[1,0,1]]示例 2text输入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]]进阶一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗解题思路这道题最大的坑点在于如果在遍历过程中直接修改矩阵新赋值的0会影响后续判断导致整个矩阵全变成0。因此我们需要采取先标记后修改的策略。下面介绍三种解法从最容易想到到最节省空间逐步优化。解法一标记数组O(mn) 空间思路这是最直观的解法。我们创建两个布尔数组row和col分别记录每一行和每一列是否需要被置零。第一次遍历矩阵如果matrix[i][j] 0则将row[i]和col[j]都标记为true。第二次遍历矩阵如果row[i]或col[j]为true则将当前位置置为 0。代码实现javaclass Solution { 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] true; 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(m n)需要两个额外数组。解法二两个标记变量O(1) 空间优化版思路能不能不使用额外数组我们可以利用矩阵的第一行和第一列来存储标记信息。具体做法用两个布尔变量rowZero和colZero记录第一行和第一列本身是否原本包含 0。从(1,1)位置开始遍历如果matrix[i][j] 0则将matrix[i][0]和matrix[0][j]标记为 0。第二次遍历从(1,1)开始如果matrix[i][0] 0或matrix[0][j] 0则将当前位置置为 0。最后根据rowZero和colZero决定是否将第一行和第一列置为 0。为什么要单独记录第一行和第一列因为第一行和第一列同时承担了存储标记的角色它们原本的状态会被覆盖。如果不提前记录我们就不知道第一行和第一列本身是否需要被置零。代码实现javaclass Solution { public void setZeroes(int[][] matrix) { int m matrix.length, n matrix[0].length; boolean rowZero false, colZero false; // 1. 记录第一行和第一列是否原本包含 0 for (int i 0; i m; i) { if (matrix[i][0] 0) colZero true; } for (int j 0; j n; j) { if (matrix[0][j] 0) rowZero true; } // 2. 使用第一行和第一列作为标记 for (int i 1; i m; i) { for (int j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] 0; matrix[0][j] 0; } } } // 3. 根据标记置零从 (1,1) 开始 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; } } } // 4. 最后处理第一行和第一列 if (rowZero) { for (int j 0; j n; j) matrix[0][j] 0; } if (colZero) { for (int i 0; i m; i) matrix[i][0] 0; } } }复杂度分析时间复杂度O(m × n)空间复杂度O(1)解法三一个标记变量极简版思路能否进一步优化只用一个标记变量答案是肯定的。我们只用colZero记录第一列是否包含 0而第一行是否包含 0 的信息可以存储在matrix[0][0]中。但这里有一个关键细节置零操作需要从最后一行开始倒序进行。因为matrix[0][0]既代表第一行的状态也代表第一列的状态如果正序处理第一行的状态可能会被提前覆盖。代码实现javaclass Solution { public void setZeroes(int[][] matrix) { int m matrix.length, n matrix[0].length; boolean colZero false; for (int i 0; i m; i) { // 检查第一列是否有 0 if (matrix[i][0] 0) colZero true; // 检查其他列并将标记存储在第一行和第一列 for (int j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] 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 (colZero) { matrix[i][0] 0; } } } }复杂度分析时间复杂度O(m × n)空间复杂度O(1)三种解法对比解法空间复杂度优点缺点标记数组O(mn)简单直观不易出错需要额外空间两个标记变量O(1)空间最优思路清晰需要单独记录第一行/列一个标记变量O(1)最节省空间倒序遍历容易写错可读性略差推荐面试时建议先给出解法一然后主动优化到解法二这样能展示你的优化思维。解法三可以作为扩展了解实际工程中更推荐解法二因为可读性更好。踩坑提醒不要边遍历边置零这是最常见的错误。如果遇到 0 就立即将整行整列置零后面遍历到的 0 可能是刚被赋值的会导致错误地多置零。注意第一行和第一列的特殊性当使用原地标记法时一定要先记录第一行和第一列的原始状态否则它们的状态会丢失。考虑边界情况如果矩阵只有一行或一列确保代码仍然能正确运行。总结这道题的核心思想是标记后置—— 先记录哪些行/列需要置零再进行修改。从 O(mn) 到 O(mn) 再到 O(1) 的空间优化过程是一道非常经典的考察原地算法的题目。掌握这三种解法不仅能帮你通过这道题更能让你对矩阵操作类的题目有更深的理解。题目链接 题解链接题目链接LeetCode 73. 矩阵置零本题题解链接LeetCode 官方题解 - 矩阵置零如果这篇文章对你有帮助欢迎点赞、收藏、关注更多 LeetCode HOT 100 题解持续更新中