Leetcode 矩阵置零
LeetCode 矩阵
2023-06-13 09:17:20 时间
题目描述(中等难度)
给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
进阶:
- 一个直观的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
- 你能想出一个仅使用常量空间的解决方案吗?
示例 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,下图第二行,第二列为零,使用红色框标识元素都需要设置成零。
解法一 (空间复杂度 O(mn))
- 使用暴力破解,复制一个矩阵备份,遍历复制矩阵,遇到零就把当前行和列重置零。 为何要使用复制矩阵呢?如果直接遍历矩阵,如果第一行第一列为零,做了重置零以后,行全部都重置为零,遍历后面的列全部都会设置成零。
解法二 (空间复杂度O(m+n))
- 优化一下解法一的算法,如果一个行或者列是零,我们只需要标记一下该行或者该列为零即可。
- 使用两个数组记录对应的行和列是否有零出现。
- 记录结束之后,遍历矩阵,如果记录的行或者列有零,元素重置零。
解法三 (空间复杂度O(1))
- 在解法二的基础上,把标记行或者列换成标记在矩阵上第一列和第一行。
- 遍历第一行,如果为零,则同列全部置为零。
- 遍历第一列,如果为零,则同行全部置为零。
- 因为遍历列是在遍历行之后,所以遍历行的时候是不能遍历第一列的。只能开始记录一个标记位,标记第一行、第一列是否存在零。
总结
- 重置零分别使用了空间复杂度O(mn)、O(m+n)、O(1)。
- 矩阵存在零就把行和列都设置成零,就需要利用好第一行和第一列这属性,存在零就在第一行和第一列设置零,对于特殊的首位置,需要添加标识。
相关文章
- LeetCode每日一题-8:重塑矩阵
- ☆打卡算法☆LeetCode 211. 添加与搜索单词 - 数据结构设计 算法解析
- LeetCode笔记:Weekly Contest 306
- LeetCode刷题系列(3)
- leetcode-17电话号码的字母组合(回溯)[通俗易懂]
- leetcode-124. 二叉树中的最大路径和(树形dp)
- leetcode 22 括号生成 js 实现
- 【day04】力扣(LeetCode)每日一刷[1306. 跳跃游戏 III ][703. 数据流中的第 K 大元素 ][1337. 矩阵中战斗力最弱的 K 行]
- leetcode 54. 螺旋矩阵 js高效实现
- 用javascript分类刷leetcode---动态规划
- 前端工程师leetcode算法面试必备-二叉树深度广度遍历1
- leetcode 二分查找 35. Search Insert Position
- LeetCode-739-每日温度
- Leetcode 111. 二叉树的最小深度
- LeetCode每日一题之817题链表组件
- LeetCode_1-两数之和
- LeetCode 知识点集成