矩阵置零最优解：从O(mn)到O(1)的原地算法与边界处理-北京尧图网络

1. 题目到底是什么——先读懂需求里的坑经常刷算法题的朋友对“矩阵置零”应该不陌生LeetCode 第 73 题。它的题干很短给定一个 m x n 的矩阵如果某个元素为 0则将其所在行和列的所有元素都设为 0要求原地操作也就是不能额外开一个同样大小的矩阵来折腾。乍一看真的很简单遍历矩阵碰到 0 就把整行整列都改掉。但你要是真这么写立刻会掉进一个隐蔽的陷阱当场把后面的元素改了遍历还没结束原本不是 0 的格子可能就被你提前改成 0 了于是它也会“触发”置零规则最后整个矩阵全变 0。这就是这道题第一个坑你不能边遍历边修改得先“记账”再“动手”。这道题适合谁去啃其实不止是准备面试的人。日常做数据处理时也经常遇到类似需求比如清洗表格时想把包含缺失值的行标记出来图像处理里做连通域标注前也可能需要先把某些关键行列隔离出来。能把这类“标记—同步—清理”的逻辑理顺写出来的代码会稳很多。我最初看到这题时也觉得 10 分钟能搞定结果真写起来发现题虽然短考点很密集空间复杂度的递进优化、原地算法如何避免信息覆盖、边界条件怎么处理。你把这题吃透了等于把“数组原地操作”这一类题的地基打了一半。1.1 一个看起来没难度的题难点藏在哪先明确一下题目细节。输入是一个二维数组 matrix它的尺寸是 m 行 n 列。要求是只要某个格子 matrix[i][j] 的值是 0那么最终结果里第 i 行、第 j 列的所有格子都要变成 0。原地操作意味着你只能修改这个矩阵本身空间复杂度尽量低。“尽量减少额外空间”是这道题最核心的限制条件。很多人在 LeetCode 上提交一个 O(mn) 空间的解法也能通过因为题目没说必须 O(1)只是“你能不能在 O(1) 的条件下做出来”才是面试官真正关心的。所以这题真正难的点不是“做出来”而是“怎么省着做”。随着空间复杂度从 O(mn) 一路压到 O(mn) 再到 O(1)你会发现每个阶段用到的思路都对应着一类经典的算法技巧。另一个容易忽略的细节是矩阵的行列可能不对称。m 和 n 都可能为 1也就是一行或者一列的退化矩阵。这种情况下你的标记逻辑必须还成立否则很容易数组越界。1.2 题目真正卡人的三个关键点我刷了三遍这题也和同事对过各自实现总结下来卡人的基本是三点第一“提前污染”。如果你第一次遍历碰到 0 后立刻把整行整列改成 0那么原本没有 0 的行也会因为你改了它的某一列而出现 0后续遍历就会误判。解决办法只有一个先记录后修改记录和修改分两步走。本质上这和“先拍照再施工”是一个道理你不能一边拆承重墙一边看图纸。第二空间和时间的权衡。这道题最自然的思路是额外开一个 m 行 n 列的布尔数组记录哪些位置是 0再统一修改。空间 O(mn)代码五分钟写出来。但如果你去面试面试官大概率会追问能不能不用 mn 的空间能不能连 mn 也不用这就是在考察你对“信息冗余”的敏感度一个矩阵里哪些信息可以由矩阵本身承载哪些必须靠外部存储。第三标记区域和真实数据混在一起后怎么区分。最优解会用矩阵的第一行和第一列做“留言板”把哪些行、哪些列要置零的信息先写上去。但问题是第一行和第一列本身也可能存在 0如果这个 0 被当作标记来读会把所有行都置零。区分“标记用的 0”和“本来存在的 0”就是 O(1) 解法里最容易出错的地方。看到这里你大概明白了这题真正的考点不在“遍历矩阵”这一动作上而在“如何用最低成本保存状态”上。2. 第一版思路用“记账本”记录再动手先别急着上最优解。我们按一个正常人的思路来推要避免污染就要先记住哪些位置是 0等遍历完了回头再统一置零。最直白的方法就是开一个和原矩阵同样大小的布尔二维数组。第一次遍历时如果 matrix[i][j] 0就在 marks[i][j] 上记 true。遍历结束后再遍历这个标记数组遇到 true 就把原矩阵对应行和列全部置零。这个解法时间复杂度是 O(mn mnm mnn)化简后约等于 O(mn(mn))。如果只看理论复杂度确实有点高。但实践中很多矩阵是稀疏的0 很少实际操作的次数会远小于理论值。2.1 思路原理先记录、后修改我第一次给同事讲这个思路时用了“考试答题卡”来类比。你在答题卡上涂答案之前得先在草稿纸上算好不能直接在答题卡上涂涂改改对吧矩阵置零也是草稿纸就是额外的标记数组。具体流程非常直白def setZeroes(matrix): m, n len(matrix), len(matrix[0]) marks [[False] * n for _ in range(m)] # 第一遍只记录不修改 for i in range(m): for j in range(n): if matrix[i][j] 0: marks[i][j] True # 第二遍根据记录统一修改 for i in range(m): for j in range(n): if marks[i][j]: for k in range(n): matrix[i][k] 0 for k in range(m): matrix[k][j] 0代码很干净逻辑完全正确。问题只有一个空间复杂度 O(mn)不够体面。别觉得 O(mn) 丢人。在很多实际业务场景中数据量不大时用这个方法完全可接受。系统设计上有一个原则叫“先保证正确再考虑优化”你连最笨的正确版本都写不出来上来就追求 O(1) 空间大概率是浪费半小时还写出一堆 Bug。先跑通再优化这个节奏是对的。2.2 优缺点与适用场景这个方法最大的优点是简单、直观、不容易错。不管矩阵多大你都不用动脑筋代码逻辑一目了然review 起来也飞快。它的缺点也很明显空间占用和矩阵面积成正比。如果是一张 10000 x 10000 的矩阵额外标记数组就是 1 亿个布尔值按 Python 的存储方式内存会非常难看。所以我的建议是这个版本适合用来“验题”也就是确认自己的思路是否覆盖了所有边界情况。面试时你可以先快速说一遍这个解法以此证明你理解问题然后再展开发散能不能优化到 O(mn)再到 O(1)这种层层递进的节奏本身就是面试官想看到的思维方式。3. 常规优化行标记和列标记分离既然完整记录的代价太高我们换个角度想一个位置是 0其实只带来了两类信息——“它所在的行需要置零”和“它所在的列需要置零”。至于这是第几行第几列交叉的那个点根本不需要单独记。于是我们可以用两个数组row_flag 长度为 mcol_flag 长度为 n。第一次遍历时只要 matrix[i][j] 0就把 row_flag[i] 置 Truecol_flag[j] 置 True。遍历结束后再根据这两个数组把对应行和对应列置零。空间复杂度降到了 O(mn)。这是非常经典的“维度拆分”思想二维的信息拆成两个一维分别记录。3.1 为什么空间能压到 O(mn)我们回到信息论的角度理解这个优化。原来的 O(mn) 记录的是什么记录的是“每一个格子是否为 0”。但实际上当我们知道“第 2 行需要置零”和“第 5 列需要置零”之后就算不知道“第 2 行第 5 列那个格子是不是 0”也能构造出最终结果。因为题目要的是整行整列置零不是单个格子置零。所以行维度和列维度天然解耦。既然解耦了记录时自然可以不耦合。这就是空间复杂度能降下来的本质原因你记录的信息粒度变粗了但它仍然足以还原出结果。这个思路在工程中也特别常见。比如权限系统里你不会给每个用户都存一份完整的菜单树而是记录“这个用户属于哪些角色”“这个角色能访问哪些资源”最后做一次笛卡尔积或交集就出来了。本质上都是利用维度之间的独立性来压缩存储。3.2 代码实现与分析代码比上一个版本还短def setZeroes(matrix): m, n len(matrix), len(matrix[0]) row_flag [False] * m col_flag [False] * n for i in range(m): for j in range(n): if matrix[i][j] 0: row_flag[i] True col_flag[j] True for i in range(m): for j in range(n): if row_flag[i] or col_flag[j]: matrix[i][j] 0第二遍遍历时不用再单独对“某一行所有列”和“某一列所有行”分别操作只需要判断当前位置所在行或所在列是否被标记。这代码写出来比第一个版本还简洁而且不容易出现重复置零的问题。这个版本的时间复杂度是 O(mn)因为只做了两次完整的双遍历比第一版的 O(mn(mn)) 要稳定得多。空间 O(mn)已经比较能打了。但还可以继续抠。面试官通常会在这个时候追问一句“能不能把空间也省掉连这两个数组都不用”如果你能接住这个问题说出 O(1) 的解法这题基本就过关了。4. 最优解把标记写进矩阵本身O(1) 空间的思路说起来很巧妙实际操作时也最容易翻车。既然矩阵里那么多格子为什么不能用矩阵自身的某些行、列来当标记我们选择第一行和第一列作为“留言板”。因为第一行和第一列最终也需要根据情况置零在最终置零之前它们就像草稿纸一样可以先帮我们记一点信息。具体做法是遍历除了第一行和第一列之外的所有格子。如果 matrix[i][j] 0就把 matrix[i][0] 和 matrix[0][j] 都设为 0。这个动作的含义是“我在第 i 行发现了 0标记在第一列上我在第 j 列发现了 0标记在第一行上。”等所有标记写完后再根据第一行和第一列上的标记去把对应的整行整列置零。但这里有个致命问题第一行和第一列自身有没有 0如果它们本来就有 0那这个 0 到底表示“这一行需要置零”还是“它只是一个格子里的 0”如果不加区分所有行都会被误置为零。4.1 用第一行第一列当“留言板”为了说清楚这件事还是举一个例子。假设矩阵是1 2 3 4 0 6 7 8 9第二行第二列是 0。我们用第一行和第一列做标记matrix[1][0] 设为 0matrix[0][1] 设为 0。这时矩阵变成1 0 3 0 0 6 7 8 9第一行第一列出现了两个额外的 0它们并不代表“第一行全部要置零”只是标记。真正要置零的是第二行和第二列。最后一步根据标记把第二行全置零第二列全置零得到1 0 3 0 0 0 7 0 9结果正确。但你再想想如果第一行本身有元素是 0比如1 0 3 4 5 6 7 8 9第一行第二列是 0所以我们本来就需要把第一行整行置零。如果直接用第一行和第一列来存标记matrix[0][0] 也会被标记而且第一行的状态会被这些标记干扰你很难判断“第一行到底需不需要置零”。所以必须有一个额外的变量单独记录“第一行原本是否出现过 0”和“第一列原本是否出现过 0”。这两个变量可以是两个布尔值放在代码里不占矩阵额外空间。4.2 写代码前必须先想清楚的三件事动手写 O(1) 解法前我会先问自己三个问题第一第一行和第一列作为“留言板”它们的原始状态怎么保全答案是用两个布尔变量 row0 和 col0在遍历最开始先把第一行和第一列里是否有 0 记下来。这两个布尔变量就是我们的“保险”。第二什么时候写标记什么时候根据标记置零顺序绝对不能错。正确顺序是先扫整个矩阵把所有需要的信息都写进第一行第一列然后根据第一行第一列的标记去把除了第一行第一列之外的行列置零最后再回头处理第一行和第一列本身。如果先把第一行置零了标记信息就丢了。第三标记信息和真实数据混在一起最后怎么还原这需要一点“逆向思维”既然第一行第一列的值已经被改过了那么保护它们原始状态的唯一办法就是提前存储并在最后阶段使用存储结果覆盖回去。想清楚这三点再写代码就不会乱。4.3 完整实现与细节说明直接贴出我实际用过的版本def setZeroes(matrix): m, n len(matrix), len(matrix[0]) # 记录第一行和第一列是否原本包含 0 first_row_has_zero any(matrix[0][j] 0 for j in range(n)) first_col_has_zero 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] 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 first_row_has_zero: for j in range(n): matrix[0][j] 0 if first_col_has_zero: for i in range(m): matrix[i][0] 0这个版本能处理各种边界。但有两个细节要特别提醒细节一first_row_has_zero和first_col_has_zero必须在任何修改之前计算完。如果你先把 matrix[0][0] 改成 0 再去判断第一行有没有 0结果就失真了。细节二第二遍遍历处理的是 i 1 且 j 1 的区域。因为第一行第一列的格子本身就是标记不能再用标记规则去置零自己。最后单独处理第一行和第一列就是为了防止标记信息把第一行整行覆盖掉。时间复杂度 O(mn)空间 O(1)。这是这道题能拿到的最优解。5. 测试和调试什么样的用例最容易翻车写完了代码别急着提交。这类“原地标记”的题目最容易在三个地方翻车第一行本身有 0、第一列本身有 0、矩阵只有一行或一列。我把自己踩过的坑整理成了测试清单分享出来给你参考。5.1 必测的几类用例第一类最基本的普通矩阵matrix [ [1, 2, 3], [4, 0, 6], [7, 8, 9] ] # 期望结果 # [1, 0, 3] # [0, 0, 0] # [7, 0, 9]第二类第一行和第一列本身就带 0matrix [ [0, 1, 1], [1, 1, 1], [1, 1, 1] ]如果写代码时不加区分常见的 Bug 是最后第一列全变成 0或者整个矩阵全变成 0。正确结果应该是第一行全 0第一列全 0中间那个 1 保留。第三类单行矩阵matrix [[1, 0, 1]]期望结果是[[0, 0, 0]]因为第二列有 0整行都应该置零。但如果你在代码里用 range(1, m)m1 时循环不会执行很容易漏掉处理。第四类单列矩阵matrix [[1], [0], [1]]期望结果是[[0], [0], [0]]同样容易因为循环范围问题漏处理。我建议你把这几类用例直接写成测试函数每次改完代码都跑一遍比手动验算快得多也安全得多。5.2 我踩过的坑和排查技巧我说一个自己真实翻过车的场景。当时我写完 O(1) 版本直接跑 LeetCode 上的测试用例前几个都过了心里还挺美。提交之后一个只有一行一列的用例直接把我打回原形。我排查了一下问题出在first_row_has_zero和后面的置零逻辑上。当矩阵只有一个格子且值为 0 时any判断是能正确识别出来的但后面的双重循环 range(1, m) 和 range(1, n) 都跳过了最后靠first_row_has_zero和first_col_has_zero分别处理时matrix[0][0] 先被置零一次再被置零一次没问题。但如果你在代码里把first_row_has_zero放在某个修改之后值就会变成 False什么都不触发结果就错了。排查这类问题我的经验是不要只盯着 LeetCode 提交结果看而是在本地写一个小的测试脚本把多维用例、单行单列用例全部打出来用断言 assert 验证。还有一个小技巧如果你用 Python 调试可以在每个阶段打印矩阵的当前状态看标记到底写到了哪里哪里被提前污染了。很多时候一眼看过去问题就暴露了。另外还要注意不要用“先置零整行再置零整列”的顺序去覆盖实现因为行列交叉处的格子会被重复置零虽然结果没错但逻辑上会产生多余的赋值。对于大矩阵这种多余操作会影响性能。6. 从这道题延伸出去的思考矩阵置零这道题刷完我最大的收获不是背住了最优解而是理解了一种通用的套路在空间受限的情况下如何利用数据自身结构保存额外信息。这个套路的变体在算法题里出现频率相当高。6.1 原地算法的通用套路原地算法常用的手段是“在原有数据上打标记”。比如把某些值改成负数、取绝对值、加上一个很大的偏移量以此记录额外信息最后再还原。典型例子是“找到数组中重复或缺失的数字”那一类题经常把数组下标当作哈希表键把元素值改为负数作为标记。矩阵置零的 O(1) 解法用的也是这个套路只不过标记和原数据之间用的是 0 而不是负数。为什么可以用 0 做标记因为最终结果本来就要把对应位置变成 0所以标记本身不需要和原数据“共存”它是一个临时状态。这里有一个很重要的思维转换临时状态和最终状态可以不是同一个值只要在过渡阶段信息不丢失即可。理解了这个你就能明白为什么代码要分成三阶段记录原始状态、写标记、用标记还原。顺序不能乱一旦乱了标记和真实数据就混在一起分不开了。我还想强调一个点很多初学者看最优解代码会觉得“巧妙”但巧妙不是目的。真正有价值的是推导过程。你从 O(mn) 到 O(mn)靠的是“行和列解耦”这个洞察从 O(mn) 到 O(1)靠的是“矩阵本身有空闲空间可以用”。每一步都有逻辑依据如果你能把这个推导讲清楚比背代码强十倍。6.2 面试官真正想考什么最后聊点面试相关的心得。矩阵置零在面试里非常受欢迎因为它能用很短的时间看出候选人的几个能力考察你是否理解“边读边写”的风险。很多人一上来就写了错误的版本面试官不会直接否定你而是让你跑一个案例你自己就能发现问题。能快速意识到“需要两步走”说明你对数据处理有敏感性。考察你的空间意识。O(mn) 的解法能用但面试官会追问怎么优化。这时候你能不能想到用两个数组替代矩阵再想到用第一行第一列替代两个数组每一步都体现着你对问题本质的理解深度。考察你的边界处理能力。第一行第一列是 0 怎么办单行单列怎么办这些细节看起来小却很暴露水平。很多刷题多的人会背代码但边界一改就露馅。根据我的经验你只需要掌握一种解法并吃透推理过程就能应对各种追问。与其背三个版本再现场背代码不如把 O(1) 版本自己推导一遍把每一步的“为什么”讲明白这比背诵有价值得多。这道题我前前后后刷过好几遍每刷一遍感受都不一样。最近一次是在给团队做代码 review 时发现有人实现了类似的功能把一个二维表格中有缺失值的行列删除。他用的正是 O(mn) 的标记数组方案代码很清楚但空间可以再优化。我把 O(1) 的思路讲给他听他第一反应是“还能这样”第二反应是“这有 Bug 吧”。我们对着用例一步步推最后他承认确实可行。这个反应我特别理解因为我第一次看到这个解法时也是这个表情。如果你也打算用最优解我建议你多写几个用例测一测把第一行、第一列带 0 的情况反复跑几遍跑顺了你就能彻底掌握它。

矩阵置零最优解：从O(mn)到O(1)的原地算法与边界处理

相关推荐

iOS工程实战清单：开发者模式、链接唤起与后台音频排坑指南

iOS开发全流程：从环境搭建、真机调试到上架准备

Windows 上通过 Cygwin 编译运行 Varnish 缓存实战指南

更多资讯

Windows第三方应用安全与系统防御：从下载到运行的全流程指南

Chrome 72绿色便携版：老电脑与Flash遗留系统的兼容方案

Text-to-CAD落地实战：从文本解析到STEP导出的工程化路径

Git Filter-Repo 实战：一键重写仓库历史，清理大文件与敏感信息

并/离网风光互补制氢合成氨容量-调度优化及Cplex求解

DeepSeek Harness桌面端深度解析：从安装配置到插件Skill部署实战

今日更新

Agent Skills 完全指南：原理、写法、安装与实战避坑

Agent Skills 实战：从 Genkit 定义到 GKE 部署与排查

Agent Skills 实战：从设计到调试的完整指南

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？