一天一道算法题(9):空间优化从O(mn)到O(1)的思路与实现解析
矩阵置零LeetCode 73题三种解法详解文章目录矩阵置零LeetCode 73题三种解法详解题目描述思路分析难点所在解法一O(mn) 空间最直观解法二O(mn) 空间改进解法三O(1) 空间最优解总结对比题目描述给定一个m x n的矩阵如果一个元素为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]]思路分析难点所在在遍历矩阵的过程中如果将遇到的0所在行和列直接变为0那么后续遍历时我们无法分辨某个位置的0是原本就有的还是被我们修改出来的。这会导致错误传播将原本不该清零的位置也清零了。解法一O(mn) 空间最直观最直接的想法是复制一个完全相同的矩阵然后遍历原矩阵遇到0就在复制的矩阵中清空对应的行和列。这样我们始终基于原始状态进行操作避免了错误传播。funcsetZeroes(matrix[][]int){// 复制矩阵temp:make([][]int,len(matrix))fori:0;ilen(matrix);i{temp[i]append([]int(nil),matrix[i]...)}// 遍历复制的矩阵在原矩阵上修改fori:0;ilen(temp);i{forj:0;jlen(temp[i]);j{iftemp[i][j]0{// 清空当前行clear(matrix[i])// 清空当前列fork:0;klen(matrix);k{matrix[k][j]0}}}}}复杂度分析时间复杂度O(mn)需要遍历矩阵两次空间复杂度O(mn)复制了一个完整的矩阵这种方法虽然直观但不符合题目对原地算法的要求。解法二O(mn) 空间改进仔细观察我们其实不需要复制整个矩阵。只需要记录哪些行和哪些列需要清零即可。用两个布尔数组分别标记row[i] true表示第 i 行需要清零col[j] true表示第 j 列需要清零funcsetZeroes(matrix[][]int){// 行标记数组row:make([]bool,len(matrix))// 列标记数组col:make([]bool,len(matrix[0]))// 第一次遍历标记需要清零的行和列fori:0;ilen(matrix);i{forj:0;jlen(matrix[0]);j{ifmatrix[i][j]0{row[i]truecol[j]true}}}// 第二次遍历根据标记清零fori:0;ilen(matrix);i{forj:0;jlen(matrix[0]);j{ifrow[i]||col[j]{matrix[i][j]0}}}}复杂度分析时间复杂度O(mn)空间复杂度O(mn)这种方法比解法一好很多但仍然不是最优解。解法三O(1) 空间最优解能否只使用常量空间答案是肯定的核心思想利用矩阵的第一行和第一列作为标记数组。用matrix[0][j]标记第 j 列是否需要清零用matrix[i][0]标记第 i 行是否需要清零但这里有个问题matrix[0][0]既属于第一行又属于第一列会产生冲突。解决方案是用两个独立变量row1和col1分别记录第一行和第一列本身是否包含 0。funcsetZeroes(matrix[][]int){// 用两个变量记录第一行、第一列是否存在 0row1,col1:1,1// 检查第一行是否有 0forj:0;jlen(matrix[0]);j{ifmatrix[0][j]0{row10break}}// 检查第一列是否有 0fori:0;ilen(matrix);i{ifmatrix[i][0]0{col10break}}// 遍历除第一行第一列外的所有元素fori:1;ilen(matrix);i{forj:1;jlen(matrix[0]);j{ifmatrix[i][j]0{// 用第一行标记列matrix[0][j]0// 用第一列标记行matrix[i][0]0}}}// 根据标记清零除第一行第一列外fori:1;ilen(matrix);i{forj:1;jlen(matrix[0]);j{ifmatrix[i][0]0||matrix[0][j]0{matrix[i][j]0}}}// 最后处理第一行ifrow10{forj:0;jlen(matrix[0]);j{matrix[0][j]0}}// 最后处理第一列ifcol10{fori:0;ilen(matrix);i{matrix[i][0]0}}}复杂度分析时间复杂度O(mn)空间复杂度O(1)注意事项必须先处理除第一行第一列外的元素最后再处理第一行和第一列如果一开始就清零第一行或第一列会破坏标记信息总结对比解法空间复杂度特点复制矩阵O(mn)最直观但不符合题目要求标记数组O(mn)简单改进但非最优第一行第一列标记O(1)最优解面试首选这道题的核心在于如何用有限的额外空间记录行和列的清零信息。从 O(mn) 到 O(mn) 再到 O(1)每一步优化都体现了空间换时间的思想转变值得细细品味。

相关新闻

Qwen-Image-Lightning深度解析:4步极速AI图像生成实战指南

Qwen-Image-Lightning深度解析:4步极速AI图像生成实战指南

Qwen-Image-Lightning深度解析:4步极速AI图像生成实战指南 【免费下载链接】Qwen-Image-Lightning 项目地址: https://ai.gitcode.com/hf_mirrors/lightx2v/Qwen-Image-Lightning Qwen-Image-Lightning是基于Qwen-Image模型的轻量化极速版本,通过…

2026/11/16 2:19:57 阅读更多 →
refcard-org-mode核心功能详解:让你的文档编辑效率翻倍

refcard-org-mode核心功能详解:让你的文档编辑效率翻倍

refcard-org-mode核心功能详解:让你的文档编辑效率翻倍 【免费下载链接】refcard-org-mode Get organized and boost your productivity with our comprehensive Org mode syntax reference card! Get a quick access to helpful tips and tricks. #orgmode #syntax…

2026/11/17 7:59:50 阅读更多 →
大麦网抢票脚本逆向工程:从零构建自动化购票系统的完整指南

大麦网抢票脚本逆向工程:从零构建自动化购票系统的完整指南

大麦网抢票脚本逆向工程:从零构建自动化购票系统的完整指南 【免费下载链接】Automatic_ticket_purchase 大麦网抢票脚本 项目地址: https://gitcode.com/GitHub_Trending/au/Automatic_ticket_purchase 你是否曾因热门演唱会门票秒光而苦恼?是否…

2026/11/16 2:19:58 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/17 8:22:52 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/17 12:46:04 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/17 12:46:04 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/17 11:26:33 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/17 12:46:05 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/17 12:46:05 阅读更多 →

日新闻

周新闻

月新闻