矩阵置零算法讲解

矩阵置零算法讲解

一、问题描述

给定一个 (m \times n) 的矩阵，如果一个元素为 (0) ，则将其所在行和列的所有元素都设为 (0) 。要求使用原地算法，即在不使用额外矩阵空间的情况下完成操作。

二、解题思路

暴力解法

最直观的想法是遍历矩阵，当遇到 (0) 元素时，直接将其所在行和列的元素置为 (0) 。但这种方法在遍历过程中会导致一些元素提前被误置为 (0) ，影响后续的遍历结果，所以单纯的暴力直接置零不可行。

标记法（使用 (O(m + n)) 额外空间）

可以使用两个数组，一个数组记录值为 (0) 的元素所在的行，另一个数组记录值为 (0) 的元素所在的列。

1. 第一次遍历矩阵，记录值为 (0) 的元素所在的行和列，分别存入对应的数组中。
2. 第二次遍历矩阵，根据记录行和列的数组，将对应行和列的元素置为 (0) 。

这种方法额外空间复杂度为 (O(m + n))