Java 中设置矩阵零

在本节中，我们将创建用于设置矩阵元素为零的 Java 程序（使用不同的逻辑）。这是编码轮面试中通常最重要的一个问题。

给定一个 m*n 的矩阵。如果矩阵中的任何元素为 0，则将其整行和整列设置为 0。请注意，执行此操作不应使用额外的数组。

例如，考虑以下矩阵。

在上面的数组中，第二行第二列的元素为 0。因此，我们将第二行和第二列的所有元素设置为 0。

让我们考虑另一个矩阵。

该问题可以通过以下三种方式解决：

1. 暴力法：使用嵌套循环和辅助空间。
2. 使用哈希表：在哈希表中存储行和列的状态。
3. 使用原地哈希：将哈希存储在矩阵的第一行和第一列中。

让我们逐一讨论上述方法。

暴力破解法

设置矩阵零点是一种朴素的方法。在此方法中，我们遍历矩阵，对于每个 0，我们将相应的行和列更新为 0。该方法非常简单，但可能导致错误的结果。

那么，正确的解决方案是什么？

解决方案步骤

1. 首先，创建一个大小为 m*n 的临时矩阵，并将其所有元素初始化为 1。
2. 现在，扫描原始矩阵。如果 A[i][j] == 0，则在新矩阵中将第 i 行和第 j 列的所有位置设置为 0。
3. 最后，将临时矩阵中的所有元素复制到原始矩阵中，并打印它们以获得所需的结果。

伪代码

在上述方法中，我们遍历了矩阵对应单元格的每一行和每一列。该方法的时间复杂度为 O(n*m(n+m))，空间复杂度为 O(n*m)（用于存储辅助矩阵）。

但是我们的任务是无需使用额外空间即可完成。以下方法演示了这一点。

使用哈希表

在此方法中，我们将使用哈希表。首先，我们将为矩阵的所有行和列创建一个哈希表，并将其设置为 false。如果任何行和列中的值更新为 true，则表示将该特定行和列的值更新为 0。

解决方案步骤

1. 创建两个哈希表，一个用于行，一个用于列，大小分别为 M 和 N。
2. 将 row[] 和 col[] 的所有值初始化为 false。
3. 现在遍历矩阵，对于每个 A[i][j] == 0，设置 row[i] = true 和 col[j] = true。
4. 完成步骤 3 后，再次遍历矩阵 A，对于任何元素 A[i][j]，如果 row[i] 或 col[j] 为 true，则将元素 A[i][j] 更新为 0。

让我们将上述步骤转换为逻辑。

伪代码

对于上述方法，时间复杂度为O(n*m)。因为创建和填充两个哈希表 [O(n+m)] + 遍历矩阵 [O(n*m)] + 更新矩阵 [O(n*m)]。因此，时间复杂度为 O(n*m)。由于我们使用了两个哈希表来存储元素，因此空间复杂度为 O(n+m)。

上述方法也不是最优的。通过使用原地哈希可以实现最优解决方案。

使用原地哈希

在此方法中，我们将行和列的哈希存储在矩阵本身中。我们可以使用矩阵的第一行和第一列来分别存储行和列的状态。第一行和第一列的状态可能会出现问题，可以使用两个变量来处理。

解决方案步骤

1. 定义两个变量firstRow和firstColumn来存储第一行和第一列的状态。将其设置为 false。
2. 使用这些行和列作为存储该行和列状态的哈希。
3. 遍历矩阵，对于每个 A[i][j] == 0，设置 A[i][0] = 0 和 col[0][j] = 0。
4. 如果 A[i][0] = true 或 A[0][i] = true，则更新矩阵（第一行和第一列除外）中的值（对于 A[i][j]）为 0。
5. 最后，更新第一行和第一列的值。

让我们将上述步骤转换为逻辑。

伪代码

上述方法的时间复杂度为O(m*n)，因为我们遍历了第一行和第一列，即O(m)和 O(n)，遍历并更新矩阵，即O(m*n)，最后更新第一行和第一列，即O(m) + O(n)。因此，时间复杂度为O(m*n)。我们没有为矩阵使用辅助数组，因此空间复杂度为O(1)。

Java 程序设置矩阵零点

以下 Java 程序使用额外的空间将元素设置为零。

SetMatrixZeros.java

输出

让我们看另一个 Java 程序，其中我们没有使用辅助空间将矩阵元素设置为零。

SetMatrixToZero.java

输出

让我们使用 Set 来解决同一个问题。

SetMatrixElementsToZero.java

输出

我们观察到在上述方法中，我们没有使用任何额外的空间。因此，这是一种有效的方法。在设置矩阵为零时，我们必须考虑这一点。