Java 中在角为 1 的矩阵中查找矩形

在本节中，我们将解决一个流行的编码问题，该问题曾由电子商务公司 Flipkart 和 Amazon 提出。此外，我们将通过不同的方法解决该问题并创建 Java 程序。

问题陈述

在一个大小为 m*n 的布尔矩阵中，我们需要判断矩阵中是否存在一个矩形或正方形，其所有角都等于 1。如果找到矩形或正方形的角为 1，则返回 true，否则返回 false。例如，考虑以下矩阵。

问题解决方案

该问题可以通过以下方法解决

• 暴力破解法
• 优化高效的方法

暴力破解法

这是一种解决问题的朴素方法。在这种方法中，首先，我们借助两个 for 循环（一个用于行，另一个用于列）遍历矩阵的行和列。它逐个遍历矩阵的每个元素。

如果我们找到一个元素为 1，这意味着 matrix[i][j]==1，我们必须在 同一行（第 i 行）但在另一列（第 j2 列） 中搜索另一个 1，并在 同一列（第 j 列）但在另一行（第 i2 行） 中搜索。除此之外，我们还必须搜索另一个角为 1 (i2, j2)。

因此，为了搜索角为 1，我们需要运行两个 for 循环，一个用于行，另一个用于列。

此外，我们还需要检查所有角是否都为 1。

让我们为上述方法编写算法。

算法

让我们在 Java 程序中实现上述方法。

MatrixRectangle1.java

输出

The given matrix forms a rectangle with 1 as the corner.

复杂度

在上述方法中，我们使用了四个 for 循环，两个用于行，两个用于列，因此时间复杂度将为 m*n*m*n，即 O(m² * n²)。

优化高效的方法

该方法为问题提供了优化的解决方案。在这种方法中，我们从第一个元素开始扫描矩阵，并逐行扫描。如果我们在同一行中找到一对 1，则将相应的索引值存储在 HashSet 中。下图描绘了这一点。

如上图所示，第一行包含一对 1，其索引值为 (0, 3)。类似地，我们将扫描第二行，并在索引 (2, 4) 处找到一对 1。

我们必须对每一行重复此过程。

这里出现一个问题，如果同一行中有多个 1 怎么办（考虑矩阵的最后一行）。为此，我们需要运行另一个 for 循环。在最后一行中，存在多对 1，即 (0, 2)、(0, 4) 和 (2, 4)。

我们观察到位置 (2, 4) 处的一对 1 已经存储在 Set 中，我们在同一列中找到了另一对 1，这意味着它形成一个矩形或正方形。

上述方法可以按以下简单步骤理解

1. 自上而下逐行遍历矩阵。
2. 对于每一行，存储 1 的每个组合并将该组合推入 HashSet 中。
3. 如果我们在同一行中再次找到该组合，我们就会得到一个矩形或正方形。

让我们在 Java 程序中实现上述方法。

MatrixRectangle2.java

输出

The given matrix forms a rectangle with 1 as the corner.

复杂度

在上述方法中，我们使用了三个 for 循环，两个用于行，一个用于列。因此，上述方法的时间复杂度将为 m*n*m，即 O(m² * n)。我们观察到与暴力方法相比，时间复杂度得到了优化。