哈尔滨市网站建设_网站建设公司_RESTful_seo优化

Java版LeetCode热题100之“矩阵置零”：从O(m+n)到O(1)空间的极致优化

摘要：本文深入剖析 LeetCode 第 73 题 “矩阵置零”，全面覆盖原题回顾、算法构思、三种解法（标记数组法、双标记变量法、单标记变量法）、代码实现、复杂度分析、面试高频问答、实际应用场景及延伸思考。我们将从最直观的思路出发，逐步演进至满足O(1) 额外空间的最优解，并揭示其背后精妙的“原地标记”思想，助你彻底掌握这一经典矩阵操作难题。

一、原题回顾

题目名称：矩阵置零
题目编号：LeetCode 73
难度等级：中等（Medium）

题目描述

给定一个m x n的矩阵，如果一个元素为0，则将其所在行和列的所有元素都设为 0。

要求：

• 必须使用原地算法（in-place algorithm）
• 进阶：能否仅使用常量级别额外空间？

示例

示例 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
• -2^31 <= matrix[i][j] <= 2^31 - 1

二、原题分析

初步观察

• 一旦发现一个0，就要将其整行整列置零
• 关键难点：不能在遍历过程中直接置零！
  • 因为新置的0会被误认为是原始0，导致错误传播
  • 例如：若先将某行置零，后续遍历时会把所有列也置零，结果全零

核心挑战

如何在不丢失原始 0 信息的前提下，完成原地修改？

解题方向

我们需要一种机制来记录哪些行/列需要被置零，然后再统一操作。

常见思路：

1. 用额外空间记录（如布尔数组）→ 空间 O(m+n)
2. 复用矩阵自身空间→ 空间 O(1)

题目进阶要求 O(1) 空间，因此我们必须探索原地标记方案。

三、答案构思

方法一：标记数组（直观但非最优）

• 创建两个布尔数组row[m]和col[n]
• 第一次遍历：记录哪些行/列有 0
• 第二次遍历：根据标记置零

✅ 优点：逻辑清晰，不易出错
❌ 缺点：空间 O(m+n)，不满足进阶要求

方法二：双标记变量（标准 O(1) 解法）

• 核心思想：用矩阵的第一行和第一列作为标记数组！
• 但第一行/列本身可能包含 0，需额外记录
• 引入两个布尔变量：
  • flagRow0：第一行是否原本有 0
  • flagCol0：第一列是否原本有 0

步骤：

1. 预处理：检查第一行/列是否有 0，记录到 flag
2. 遍历其余部分（i≥1, j≥1）：若matrix[i][j]==0，则标记matrix[i][0]=0和matrix[0][j]=0
3. 再次遍历其余部分：若matrix[i][0]==0或matrix[0][j]==0，则置零
4. 最后根据 flag 更新第一行/列

方法三：单标记变量（极致优化）

• 进一步优化：只用一个变量flagCol0
• 利用matrix[0][0]同时表示“第一行是否有 0”
• 但需注意：更新顺序必须从下往上、从右往左，防止提前覆盖标记

💡 三种方法时间复杂度均为 O(mn)，但空间从 O(m+n) → O(1)

四、完整答案（Java 实现）

方法一：标记数组法（O(m+n) 空间）

classSolution{publicvoidsetZeroes(int[][]matrix){intm=matrix.length;intn=matrix[0].length;// 创建标记数组boolean[]row=newboolean[m];boolean[]col=newboolean[n];// 第一次遍历：记录 0 的位置for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(matrix[i][j]==0){row[i]=true;col[j]=true;}}}// 第二次遍历：根据标记置零for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(row[i]||col[j]){matrix[i][j]=0;}}}}}

方法二：双标记变量法（推荐，清晰稳定）

classSolution{publicvoidsetZeroes(int[][]matrix){intm=matrix.length;intn=matrix[0].length;// 标记第一列和第一行是否原本包含 0booleanflagCol0=false;booleanflagRow0=false;// 检查第一列for(inti=0;i<m;i++){if(matrix[i][0]==0){flagCol0=true;break;}}// 检查第一行for(intj=0;j<n;j++){if(matrix[0][j]==0){flagRow0=true;break;}}// 遍历除第一行/列外的部分，用第一行/列做标记for(inti=1;i<m;i++){for(intj=1;j<n;j++){if(matrix[i][j]==0){matrix[i][0]=0;// 标记第 i 行matrix[0][j]=0;// 标记第 j 列}}}// 根据第一行/列的标记，置零其余部分for(inti=1;i<m;i++){for(intj=1;j<n;j++){if(matrix[i][0]==0||matrix[0][j]==0){matrix[i][j]=0;}}}// 最后处理第一列if(flagCol0){for(inti=0;i<m;i++){matrix[i][0]=0;}}// 最后处理第一行if(flagRow0){for(intj=0;j<n;j++){matrix[0][j]=0;}}}}

方法三：单标记变量法（极致优化）

classSolution{publicvoidsetZeroes(int[][]matrix){intm=matrix.length;intn=matrix[0].length;booleanflagCol0=false;// 第一次遍历：同时记录第一列是否有 0，并标记其余位置for(inti=0;i<m;i++){if(matrix[i][0]==0){flagCol0=true;}for(intj=1;j<n;j++){if(matrix[i][j]==0){matrix[i][0]=0;// 标记行matrix[0][j]=0;// 标记列}}}// 从下往上、从右往左更新，防止覆盖标记for(inti=m-1;i>=0;i--){for(intj=n-1;j>=1;j--){if(matrix[i][0]==0||matrix[0][j]==0){matrix[i][j]=0;}}// 处理第一列if(flagCol0){matrix[i][0]=0;}}}}

✅建议：面试时优先写方法二（逻辑清晰），再提方法三作为优化。

五、代码分析

方法一：标记数组法

• 两次遍历：第一次记录，第二次更新
• 空间开销：m + n个布尔值
• 适用场景：当空间不是瓶颈，且追求代码可读性时

方法二：双标记变量法（重点！）

步骤详解

1. 预处理第一行/列：

   • 单独检查，因为它们将被用作标记区
   • 用flagRow0和flagCol0保存原始状态

2. 标记阶段（i≥1, j≥1）：

   • 若matrix[i][j]==0，则：
     • matrix[i][0] = 0→ 表示第 i 行需置零
     • matrix[0][j] = 0→ 表示第 j 列需置零

3. 更新阶段（i≥1, j≥1）：

   • 若行标记或列标记为 0，则置零

4. 最后更新第一行/列：

   • 根据预存的 flag 决定是否置零

示例演示：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

1. 预处理：

   • 第一列：[0,3,1]→ 有 0 →flagCol0 = true
   • 第一行：[0,1,2,0]→ 有 0 →flagRow0 = true

2. 标记阶段（遍历 i=1~2, j=1~3）：

   • 无其他 0，所以第一行/列保持[0,1,2,0]和[0,3,1]^T

3. 更新阶段：

   • 所有位置因第一行/列为 0 而被置零？不！
   • 实际上，只有(1,1)~(2,3)被检查：
     • 因matrix[1][0]=3≠0且matrix[0][1]=1≠0→ 不置零？等等！

❗ 注意：在标记阶段，我们没有修改第一行/列的非0值！

• 原始第一行是[0,1,2,0]，所以matrix[0][1]=1,matrix[0][2]=2
• 但在更新阶段，我们会检查matrix[0][j]是否为 0
• 只有j=0和j=3时matrix[0][j]==0，所以只有这些列会被置零

最终结果正确：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

方法三：单标记变量法

关键技巧：倒序更新

• 为什么从i = m-1到0？
  • 因为matrix[i][0]是行标记，若从上往下更新，会提前覆盖下面的标记
• 为什么j从n-1到1？
  • 同理，防止覆盖列标记matrix[0][j]

如何用matrix[0][0]表示第一行？

• 在第一次遍历中，若matrix[0][j]==0（j≥1），则matrix[0][0]会被设为 0
• 但若只有matrix[0][0]==0，它本身就表示第一行有 0
• 因此，matrix[0][0]==0⇨ 第一行需置零

⚠️ 但第一列需单独用flagCol0记录，因为matrix[0][0]已被用于第一行

六、时间复杂度与空间复杂度分析

详细分析

• 时间复杂度：

  • 所有方法都进行常数次遍历（2~3 次）
  • 每次遍历访问 mn 个元素 → 总 O(mn)

• 空间复杂度：

  • 方法一：需 m+n 个布尔值 → O(m+n)
  • 方法二/三：仅用 1~2 个布尔变量 → O(1)

✅ 方法二和三是满足题目“进阶要求”的标准答案。

七、常见问题解答（FAQ）

Q1：为什么不能在第一次遍历时直接置零？

A：会导致错误传播。

• 例如：[[1,0,1]]，若遇到 0 立即置零整行 →[0,0,0]
• 但若后面还有其他行，这些新 0 会被误认为原始 0，导致更多列被置零

Q2：方法二中，为什么先处理非第一行/列，最后才处理第一行/列？

A：因为第一行/列被用作标记存储区。

• 如果提前修改它们，会丢失原始 0 信息
• 所以必须最后根据预存的 flag 来决定是否置零

Q3：方法三中，为什么更新要倒序？

A：防止覆盖尚未使用的标记。

• 假设从上往下更新：
  • 更新第 0 行时，可能将matrix[0][j]设为 0
  • 但第 1 行的更新依赖matrix[0][j]的原始标记值
  • 提前修改会导致错误

Q4：如果矩阵全是 0，算法还正确吗？

A：完全正确！

• 方法二：flagRow0 = flagCol0 = true
• 标记阶段：所有matrix[i][0]和matrix[0][j]保持 0
• 更新阶段：所有元素被置零
• 最后第一行/列也被置零 → 结果全零 ✅

Q5：负数会影响结果吗？

A：不会。算法只关心是否等于 0，与正负无关。

八、优化思路总结

工程建议：

• 优先选择双标记变量法：平衡了可读性与效率
• 单标记变量法适合对空间极度敏感的嵌入式场景

九、数据结构与算法基础知识点回顾

1. 原地算法（In-place Algorithm）

• 定义：仅使用常数额外空间，直接在输入数据结构上修改
• 优势：节省内存，提高缓存局部性
• 挑战：需小心处理数据依赖和覆盖问题

2. 空间复用（Space Reuse）

• 将输入结构的一部分用作辅助存储
• 常见于数组/矩阵问题（如本题、缺失正数）
• 关键：确保复用区域的信息可被恢复或已备份

3. 遍历顺序的重要性

• 正序 vs 倒序：影响数据依赖的正确性
• 本题中，倒序更新防止了标记被提前覆盖
• 类似思想见于“接雨水”、“股票买卖”等 DP 问题

4. 边界条件处理

• 第一行/列：特殊处理，因其被用作标记区
• 单行/单列矩阵：需确保循环边界正确
  • 例如：m=1时，方法二中i>=1的循环不会执行，仅靠 flag 处理

十、面试官提问环节（模拟对话）

Q：你的解法修改了原矩阵，如果要求不能修改呢？

A：若不能修改原矩阵，则必须使用额外空间存储结果。

• 最小空间：O(mn)（新建矩阵）
• 或 O(m+n)（记录行列，再新建矩阵）
• 但无法做到 O(1) 空间，因为输出本身是 O(mn)

Q：方法三中，如果先更新第一列再更新其他列，会怎样？

A：会导致错误。

• 例如：若flagCol0=true，先将matrix[i][0]=0
• 但后续更新matrix[i][j]时，会因matrix[i][0]==0而错误置零
• 即使该行原本不应置零（仅因第一列有 0）

Q：能否用位运算进一步优化？

A：理论上可以用 bitset 压缩标记数组，但：

• 空间仍是 O(m+n)（只是常数因子更小）
• 且题目要求 O(1) 空间，不符合
• 本题的 O(1) 解法必须依赖原矩阵

Q：如果矩阵非常大（如 10000x10000），你的解法会有性能问题吗？

A：时间复杂度 O(mn) 是最优的（必须访问每个元素）。

• 但可以考虑并行化：将矩阵分块，每块独立标记，最后合并
• 不过本题的原地标记法天然串行，难以并行

Q：你的方法能处理浮点数矩阵吗？

A：不能直接处理。

• 浮点数的 0 判断需考虑精度（如abs(x) < eps）
• 且题目给定整数矩阵，无需考虑

十一、这道算法题在实际开发中的应用

虽然“矩阵置零”看似抽象，但其思想在多个领域有实际价值：

1. 数据清洗与隐私保护

• 在数据分析中，某些敏感字段（如身份证后四位为 0000）需整行/列脱敏
• 本题算法可用于批量标记并清除敏感数据

2. 图像处理中的掩码操作

• 图像可视为矩阵，0 表示透明或无效像素
• 若检测到某个关键点为 0，需将其所在行/列设为透明（如去除水印干扰）
• 本题提供了一种高效的原地掩码生成方法

3. 电子表格软件（如 Excel）

• 用户选中单元格并点击“清空整行整列”
• 软件需高效实现此类操作，尤其在大型表格中
• 原地算法可减少内存占用，提升响应速度

4. 稀疏矩阵压缩

• 在科学计算中，稀疏矩阵常用 CSR/CSC 格式存储
• 若某行/列全零，可从存储结构中移除
• 本题的标记思想可用于快速识别全零行/列

5. 游戏开发中的地图编辑

• 地图用矩阵表示，0 表示障碍物
• 若玩家放置一个“清除器”，可清除其所在行/列的障碍
• 本题算法可实时更新地图状态

📌 核心价值：高效处理“行列联动”的批量更新操作

十二、相关题目推荐

掌握本题后，可挑战以下变种或进阶题：

十三、总结与延伸

核心收获

1. 原地标记是解决矩阵/数组批量更新问题的有效手段
2. 复用输入结构的空间可将空间复杂度降至 O(1)
3. 遍历顺序对算法正确性至关重要（正序 vs 倒序）
4. 边界区域（如第一行/列）常需特殊处理

延伸思考

• 能否扩展到三维数组？
  → 可以！用第一层、第一行、第一列作为标记，但需更多 flag 变量

• 如果要求“置1”而不是“置0”？
  → 思路相同，但需注意：若原矩阵有 1，会与新置的 1 混淆
  → 需用其他标记方式（如负数、偏移量）

• 流式矩阵场景：矩阵逐行到来，如何实时维护置零状态？
  → 需要记录哪些列已出现 0，空间至少 O(n)，无法 O(1)

最后建议

• 面试时：先写标记数组法，再优化到双标记变量法
• 刷题时：手动模拟方法二的执行过程，加深理解
• 工程中：若矩阵不大，优先用标记数组法（可读性高）；若内存紧张，用双标记法

结语：“矩阵置零”是一道经典的原地算法题，它完美展示了如何在有限空间内，通过巧妙利用数据结构自身来完成复杂操作。掌握它，你不仅学会了一道题，更掌握了一种在资源受限环境下进行高效矩阵操作的思维方式。

愿你在算法征途中，纵横矩阵，游刃有余！🚀

字数统计：约 9100 字（含代码与表格）
适用读者：LeetCode 刷题者、Java 开发者、算法面试准备者
版权声明：本文为原创技术博客，转载请注明出处。