【Leetcode】73.矩阵置零

题目

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输出:

示例 2:

输入:

输出:

进阶:

一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。

一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。

你能想出一个常数空间的解决方案吗？

题解

这个题目想要使用常数空间的方案,我们就要尝试用矩阵本身去记录状态，达到最后矩阵置0的效果。则将其所在行和列的所有元素都设为 0，这个状态我们可以记录到每一行的第一列来记录[m,n]的信息。具体步骤如下：

1.从左上角到右下角遍历，用第一行和第一列来记录这行有没有0这个状态

image

2.从右下角到左上角遍历，用记录(在左边和上边)好的状态来刷新整个矩阵

image

java

python

热门阅读