73. 矩阵置零

73. 矩阵置零

已解答

中等

提示

给定一个mxn的矩阵，如果一个元素为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.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

📝 核心笔记：矩阵置零 (标记数组法)

1. 核心思想 (一句话总结)

“先记账，后清算”。

不能遍历到一个 0 就立刻把整行整列变 0（因为这会污染后续的遍历，导致全变成 0）。

必须先用两个辅助数组把“哪些行、哪些列坏了”记录下来，最后统一执行死刑。

2. 算法流程 (两遍扫描)

1. 第一遍 (记录)：遍历矩阵，只要发现matrix[i][j] == 0，就在小本本上记下：row[i] = true，col[j] = true。
2. 第二遍 (执行)：再次遍历矩阵，只要当前格子所在的行或列被记过，就将该格设为 0。

🔍 代码回忆清单 (带注释版)

// 题目：LC 73. 矩阵置零 class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; // 关键点1：空间复杂度 O(m+n) 的辅助数组 boolean[] rowHasZero = new boolean[m]; boolean[] colHasZero = new boolean[n]; // 阶段一：扫描并标记 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { rowHasZero[i] = true; // 标记第 i 行要死 colHasZero[j] = true; // 标记第 j 列要死 } } } // 阶段二：根据标记置零 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 关键点2：是“或”的关系。只要占一条，就得变0 if (rowHasZero[i] || colHasZero[j]) { matrix[i][j] = 0; } } } } }

⚡ 快速复习 CheckList (易错点)

• [ ]为什么不能一边遍历一边置零？

• • 因为如果把matrix[i][j]变成 0，下一步遍历到它时，会被误认为是原始的 0，导致把不该置零的行/列也置零了（类似病毒扩散）。必须状态分离。

• [ ]空间复杂度是多少？

• • $O(m + n)$。使用了两个 boolean 数组。

• [ ]逻辑关系？

• • 第二步判断时是row[i] || col[j](只要有一头是0，这个交叉点就是0)。

🚀 进阶提示 (面试高频追问)

你当前的代码是标准解法 ($O(m+n)$ 空间)。

面试官有 90% 的概率 会追问：“能把空间优化到 $O(1)$ 吗？”

$O(1)$思路回顾：

• 不创建新数组，直接利用矩阵的第一行和第一列来代替rowHasZero和colHasZero数组。
• 但要额外用两个变量记录“第一行本身有没有0”和“第一列本身有没有0”，防止第一行/列被内部数据污染。