【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

热门阅读

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180921A0D51J00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券