题目
给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输出:
示例 2:
输入:
输出:
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗?
题解
这个题目想要使用常数空间的方案,我们就要尝试用矩阵本身去记录状态,达到最后矩阵置0的效果。则将其所在行和列的所有元素都设为 0,这个状态我们可以记录到每一行的第一列来记录[m,n]的信息。具体步骤如下:
1.从左上角到右下角遍历,用第一行和第一列来记录这行有没有0这个状态
image
2.从右下角到左上角遍历,用记录(在左边和上边)好的状态来刷新整个矩阵
image
java
python
热门阅读
领取专属 10元无门槛券
私享最新 技术干货