示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 doocs/leetcode 仓库中的 题目文档 及其英文版为骨架完整拆解 LeetCode 73「矩阵置零」的题目定义、核心难点与进阶要求系统讲解「数组标记」与「原地标记」两条解法路径并给出 Python3、Java、C、Go、TypeScript、Rust、JavaScript、C# 共 8 种语言的完整实现与源码级对照。读完本文你将掌握这道经典矩阵题从 O(mn) 复制到 O(1) 常量空间原地算法的完整演进思路并能在实际工程中正确选择标记策略。一、题目理解问题定义、示例与约束1.1 问题定义给定一个m x n的整数矩阵matrix如果某个元素为0则将其所在行和列的所有元素都设为0。题目明确要求使用原地in-place算法完成即不能返回一个新矩阵只能直接修改传入的matrix。用符号语言描述设矩阵为matrix[i][j]若存在matrix[i][j] 0则对任意j有matrix[i][j] 0对任意i有matrix[i][j] 0。1.2 示例与示意图示例 1输入matrix [[1,1,1],[1,0,1],[1,1,1]]中间的0使其所在的行与列全部置零输出[[1,0,1],[0,0,0],[1,0,1]]。示例 2输入matrix [[0,1,2,0],[3,4,5,2],[1,3,1,5]]第一行第 1、4 列存在两个0对应的两列以及整个第一行被置零输出[[0,0,0,0],[0,4,5,0],[0,3,1,0]]。1.3 数据范围与约束m matrix.lengthn matrix[0].length1 m, n 200矩阵至少为 1×1-2^31 matrix[i][j] 2^31 - 1元素取值覆盖整个 32 位有符号整数范围因此不能用特殊值如-1或INT_MIN充当临时标记这一点在思考常量空间方案时尤为重要。1.4 进阶要求Follow up题目附带的进阶提示给出了三条循序渐进的约束使用O(mn)额外空间的直观方案如复制整份矩阵再写回不是一个好方案一个简单的改进是使用O(m n)额外空间如两个标记数组但这仍然不是最优解能否设计一个**仅使用常量空间O(1)**的解决方案这三点实际上划定了本文两条解法的坐标轴O(mn)的数组标记是达标线O(1)的原地标记才是冲刺线。二、核心难点为什么不能边扫描边清零初看题目最容易想到的做法是遍历矩阵一遇到0就立刻把它所在的行、列全部清零。但这一做法有一个致命缺陷——信息污染。假设遍历到matrix[i][j] 0时立即把整行整列清零那么这些新产生的0会覆盖尚未扫描到的区域当遍历继续推进时我们无法区分某个位置上的0是矩阵原有的、还是由先前清零操作制造出来的从而可能把不该清零的行列也一并清零导致结果错误。换个角度如果复制一份O(mn)的矩阵作为原始快照在第一份上只做标记、在第二份上写结果可以完美避开信息污染。但进阶要求明确否定了这笔空间开销。因此正确解法必须遵循一个共同原则第一遍遍历只记录哪些行、哪些列需要置零第二遍遍历再统一执行置零把收集信息与修改数据两个阶段彻底分离。两道题解的差异只在于用什么来记录。三、解法一数组标记O(m n) 额外空间3.1 算法思路设矩阵行数为m、列数为n。用长度为m的布尔数组row记录哪些行需要置零用长度为n的布尔数组col记录哪些列需要置零。整个过程分两遍扫描第一遍打标记遍历整个矩阵若matrix[i][j] 0则将row[i] true、col[j] true。此阶段只更新标记数组不动矩阵本身第二遍执行清零再次遍历整个矩阵若row[i]或col[j]为true则把matrix[i][j]置为0。由于标记数组记录的是该行/该列是否含零这一不依赖扫描顺序的事实两遍扫描之间互不干扰天然规避了第二节所述的信息污染问题。原文档的思考块Thinking也明确指出m, n 200两遍扫描在时间上完全可行额外空间从O(mn)降到O(mn)但尚未达到进阶要求的常量空间。3.2 复杂度分析时间复杂度O(m × n)两遍完整遍历每遍都是m × n个元素空间复杂度O(m n)即row数组长度m与col数组长度n之和。其中m、n分别为矩阵的行数和列数。3.3 参考实现多语言以下 8 种语言的实现均出自 doocs/leetcode 仓库的 Solution 系列源码与 题目文档 完全一致。Python3class Solution: def setZeroes(self, matrix: List[List[int]]) - None: m, n len(matrix), len(matrix[0]) row [False] * m col [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: row[i] col[j] True for i in range(m): for j in range(n): if row[i] or col[j]: matrix[i][j] 0Javaclass 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] 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; } } } } }Cclass Solution { public: void setZeroes(vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); vectorbool row(m); vectorbool col(n); for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 0) { row[i] 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; } } } } };Gofunc setZeroes(matrix [][]int) { row : make([]bool, len(matrix)) col : make([]bool, len(matrix[0])) for i : range matrix { for j, x : range matrix[i] { if x 0 { row[i] true col[j] true } } } for i : range matrix { for j : range matrix[i] { if row[i] || col[j] { matrix[i][j] 0 } } } }TypeScript/** Do not return anything, modify matrix in-place instead. */ function setZeroes(matrix: number[][]): void { const m matrix.length; const n matrix[0].length; const row: boolean[] Array(m).fill(false); const col: boolean[] Array(n).fill(false); for (let i 0; i m; i) { for (let j 0; j n; j) { if (matrix[i][j] 0) { row[i] col[j] true; } } } for (let i 0; i m; i) { for (let j 0; j n; j) { if (row[i] || col[j]) { matrix[i][j] 0; } } } }Rustimpl Solution { pub fn set_zeroes(matrix: mut VecVeci32) { let m matrix.len(); let n matrix[0].len(); let mut row vec![false; m]; let mut col vec![false; n]; for i in 0..m { for j in 0..n { if matrix[i][j] 0 { row[i] true; col[j] true; } } } for i in 0..m { for j in 0..n { if row[i] || col[j] { matrix[i][j] 0; } } } } }JavaScript/** * param {number[][]} matrix * return {void} Do not return anything, modify matrix in-place instead. */ var setZeroes function (matrix) { const m matrix.length; const n matrix[0].length; const row Array(m).fill(false); const col Array(n).fill(false); for (let i 0; i m; i) { for (let j 0; j n; j) { if (matrix[i][j] 0) { row[i] col[j] true; } } } for (let i 0; i m; i) { for (let j 0; j n; j) { if (row[i] || col[j]) { matrix[i][j] 0; } } } };C#public class Solution { public void SetZeroes(int[][] matrix) { int m matrix.Length, n matrix[0].Length; bool[] row new bool[m], col new bool[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; } } } } }3.4 仓库源码对照上述实现可直接在仓库对应源码文件中找到例如 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs与文档中的题解逐字对应可直接复制运行。四、解法二原地标记O(1) 额外空间4.1 算法思路解法一仍需要O(mn)的标记数组而进阶要求把额外空间压到O(1)。原地标记方案的核心洞察是矩阵自身的第一行与第一列完全可以充当行标记数组和列标记数组——第一行记录哪些列需要置零第一列记录哪些行需要置零。具体分四步记录首行、首列的原始状态由于第一行、第一列既要充当标记区又保存着原有数据我们必须先用两个布尔变量i0、j0分别记录第一行本身是否含零第一列本身是否含零否则标记写入会覆盖掉它们原有的信息内部打标记遍历i 1、j 1的内部区域若matrix[i][j] 0则把matrix[i][0] 0标记第i行、matrix[0][j] 0标记第j列内部执行清零再次遍历内部区域若matrix[i][0] 0或matrix[0][j] 0则把matrix[i][j]置零收尾处理首行首列若i0为真将第一行整行置零若j0为真将第一列整列置零。原文档的思考块Thinking特别强调了一个时序陷阱必须先记录i0、j0再处理内部最后才根据i0、j0清理第一行与第一列——因为第一行、第一列同时充当标记载体若过早清零标记信息会被提前覆盖导致内部清零判断失效。这正是该方案与朴素思路最大的不同之处。4.2 复杂度分析时间复杂度O(m × n)与解法一相同两遍内部扫描加上首行首列的线性清理空间复杂度O(1)除两个布尔变量i0、j0外不额外开辟与m、n相关的数组。其中m、n分别为矩阵的行数和列数。4.3 参考实现多语言以下 8 种语言的实现均出自 doocs/leetcode 仓库的 Solution2 系列源码与 题目文档 完全一致。Python3class Solution: def setZeroes(self, matrix: List[List[int]]) - None: m, n len(matrix), len(matrix[0]) i0 any(v 0 for v in matrix[0]) j0 any(matrix[i][0] 0 for i in range(m)) for i in range(1, m): for j in range(1, n): if matrix[i][j] 0: matrix[i][0] matrix[0][j] 0 for i in range(1, m): for j in range(1, n): if matrix[i][0] 0 or matrix[0][j] 0: matrix[i][j] 0 if i0: for j in range(n): matrix[0][j] 0 if j0: for i in range(m): matrix[i][0] 0Javaclass Solution { public void setZeroes(int[][] matrix) { int m matrix.length, n matrix[0].length; boolean i0 false, j0 false; for (int j 0; j n; j) { if (matrix[0][j] 0) { i0 true; break; } } for (int i 0; i m; i) { if (matrix[i][0] 0) { j0 true; break; } } 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; } } } 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; } } } if (i0) { for (int j 0; j n; j) { matrix[0][j] 0; } } if (j0) { for (int i 0; i m; i) { matrix[i][0] 0; } } } }Cclass Solution { public: void setZeroes(vectorvectorint matrix) { int m matrix.size(), n matrix[0].size(); bool i0 false, j0 false; for (int j 0; j n; j) { if (matrix[0][j] 0) { i0 true; break; } } for (int i 0; i m; i) { if (matrix[i][0] 0) { j0 true; break; } } 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; } } } 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; } } } if (i0) { for (int j 0; j n; j) { matrix[0][j] 0; } } if (j0) { for (int i 0; i m; i) { matrix[i][0] 0; } } } };Gofunc setZeroes(matrix [][]int) { m, n : len(matrix), len(matrix[0]) i0, j0 : false, false for j : 0; j n; j { if matrix[0][j] 0 { i0 true break } } for i : 0; i m; i { if matrix[i][0] 0 { j0 true break } } for i : 1; i m; i { for j : 1; j n; j { if matrix[i][j] 0 { matrix[i][0], matrix[0][j] 0, 0 } } } for i : 1; i m; i { for j : 1; j n; j { if matrix[i][0] 0 || matrix[0][j] 0 { matrix[i][j] 0 } } } if i0 { for j : 0; j n; j { matrix[0][j] 0 } } if j0 { for i : 0; i m; i { matrix[i][0] 0 } } }TypeScript/** Do not return anything, modify matrix in-place instead. */ function setZeroes(matrix: number[][]): void { const m matrix.length; const n matrix[0].length; const i0 matrix[0].includes(0); const j0 matrix.map(row row[0]).includes(0); for (let i 1; i m; i) { for (let j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] 0; matrix[0][j] 0; } } } for (let i 1; i m; i) { for (let j 1; j n; j) { if (matrix[i][0] 0 || matrix[0][j] 0) { matrix[i][j] 0; } } } if (i0) { matrix[0].fill(0); } if (j0) { for (let i 0; i m; i) { matrix[i][0] 0; } } }JavaScript/** * param {number[][]} matrix * return {void} Do not return anything, modify matrix in-place instead. */ var setZeroes function (matrix) { const m matrix.length; const n matrix[0].length; let i0 matrix[0].some(v v 0); let j0 false; for (let i 0; i m; i) { if (matrix[i][0] 0) { j0 true; break; } } for (let i 1; i m; i) { for (let j 1; j n; j) { if (matrix[i][j] 0) { matrix[i][0] 0; matrix[0][j] 0; } } } for (let i 1; i m; i) { for (let j 1; j n; j) { if (matrix[i][0] 0 || matrix[0][j] 0) { matrix[i][j] 0; } } } if (i0) { for (let j 0; j n; j) { matrix[0][j] 0; } } if (j0) { for (let i 0; i m; i) { matrix[i][0] 0; } } };C#public class Solution { public void SetZeroes(int[][] matrix) { int m matrix.Length, n matrix[0].Length; bool i0 matrix[0].Contains(0), j0 false; for (int i 0; i m; i) { if (matrix[i][0] 0) { j0 true; break; } } 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; } } } 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; } } } if (i0) { for (int j 0; j n; j) { matrix[0][j] 0; } } if (j0) { for (int i 0; i m; i) { matrix[i][0] 0; } } } }4.4 仓库源码对照原地标记版实现可在 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts、Solution2.js、Solution2.cs 中找到注意 Rust 版在本目录下未提供 Solution2 文件其余语言均已覆盖。它们与 README_EN.md 中展示的代码逐行一致可用于本地运行验证。五、两种解法对比与选型建议维度解法一数组标记解法二原地标记标记载体独立布尔数组row[m]、col[n]矩阵首行、首列自身额外空间O(m n)O(1)仅i0、j0两个布尔变量时间复杂度O(m × n)O(m × n)实现复杂度简单直观两遍遍历略高需处理首行首列的信息保存与收尾时序是否满足进阶满足第 2 条未达第 3 条满足第 3 条常量空间适用场景面试讲解、快速 AC、可读性优先追求最优空间、资源受限环境从源码结构看仓库为同一题目维护了Solution.*与Solution2.*两套实现正是为了同时沉淀这两种复杂度档位的标准解法供读者按需取用。六、边界情况与易错点结合题目约束与两种解法以下几点最容易踩坑首行或首列本身含零解法二中若忘记用i0、j0保存首行首列的原始状态清理内部时会把标记区清掉导致最终首行首列被错误处理。i0、j0是常量空间方案正确性的关键。单行或单列矩阵当m 1或n 1时矩阵退化为线性结构。此时解法二的内部区域为空整个逻辑退化为首行或首列是否含零的简单判断代码依然正确但值得手动推演一遍确认。全零矩阵所有元素均为0第一遍打标记会把所有行列都标记上结果整个矩阵仍为全零符合预期解法二中i0、j0与内部标记会同时生效结果一致。无零矩阵标记数组全为false第二遍不做任何修改矩阵原样返回。这验证了两阶段分离方案的幂等性。特殊值陷阱由于元素取值范围覆盖-2^31到2^31 - 1不能依赖某个特定值充当标记位解法二规避该问题的办法是用位置首行首列而非取值来承载标记信息。七、总结与延伸LeetCode 73「矩阵置零」是一道非常典型的原地算法 空间复杂度阶梯训练题它先引导你否定O(mn)的复制方案指出信息污染的根本矛盾再用O(mn)的数组标记给出第一档达标解强调收集信息与执行修改的两阶段分离最后借矩阵首行首列充当标记的技巧把额外空间压到O(1)完成进阶闭环。这一用数据结构自身冗余空间承载中间状态的思维与许多经典原地技巧如原地哈希、快慢指针等一脉相承。掌握本题后不妨继续在 doocs/leetcode 仓库中检索Matrix标签下的其他题目例如将首行首列标记思想迁移到更多矩阵类问题上进一步巩固原地算法的设计直觉。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 73. 矩阵置零Set Matrix Zeroes从 O(mn) 标记到 O(1) 原地算法的两种解法详解LeetCode 73. 矩阵置零Set Matrix Zeroes从 O mn 标记到 O 1 原地算法的两种解法详解 矩阵置零是一道经典的原地in示例工程LeetCode 73 Set Matrix Zeroes 全解从 O(m·n) 空间暴力法到 O(1) 原地标记leetcode 仓库多语言实现LeetCode 73 Set Matrix Zeroes 全解从 O m·n 空间暴力法到 O 1 原地标记leetcode 仓库多语言实现 导读 本文示例工程LeetCode 74. 搜索二维矩阵O(log(m×n)) 逻辑展开二分与 O(mn) 行列夹逼全解多语言实现LeetCode 74. 搜索二维矩阵O log m×n 逻辑展开二分与 O mn 行列夹逼全解多语言实现 本篇技术指南围绕 doocs/leetcod示例工程上一篇ES6 Map与数组转换完全指南10个实用技巧轻松掌握下一篇突破科学计算API文档困境Swagger UI与Julia无缝集成方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考