Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector<bool> clearRow(m), clearCol(n); for(int i=0; i<m; i++) { for(int j=0; j<n; j++){ if(!matrix[i][j]) { clearRow[i] = true; clearCol[j] = true; } } } for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(clearRow[i] || clearCol[j]) { matrix[i][j] = 0;; } } } }
Space Complexity: O(M+N).
void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); bool clear1stRow = false, clear1stCol = false; for(int i=0; i<m; i++) { if(!matrix[i][0]) { clear1stCol = true; break; } } for(int j=0; j<n; j++){ if(!matrix[0][j]) { clear1stRow = true; break; } } for(int i=1; i<m; i++) { for(int j=1; j<n; j++) { if(!matrix[i][j]) { matrix[0][j] = 0; matrix[i][0] = 0; } } } for(int i=1; i<m; i++) { for(int j=1; j<n; j++) { if(!matrix[i][0] || !matrix[0][j]) { matrix[i][j] = 0; } } } if(clear1stRow) { matrix[0].assign(n,0); } if(clear1stCol) { for(int i=0; i<m; i++) { matrix[i][0] = 0; } } }
Space Complexity: O(1)
相关推荐
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
不会LeetCode_645--Set-Mismatch 集合 S 最初包含从 1 到 n 的数字。 但不幸的是,由于数据错误,集合中的一个数字与集合中的另一个数字重复,导致一个数字重复而另一个数字丢失。 给定一个数组 nums 表示该集合在...
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...
leetcode 答案Leetcode---算法 我对 Leetcode 算法问题的回答