题目描述（中等难度）
给定一个 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)。
- 矩阵存在零就把行和列都设置成零，就需要利用好第一行和第一列这属性，存在零就在第一行和第一列设置零，对于特殊的首位置，需要添加标识。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/22139.html
