布尔矩阵问题

引言

首先，让我们了解什么是布尔矩阵问题。

我们可以说布尔矩阵问题是一个可以操作矩阵的问题，其中矩阵元素的值为真或假。借助这个问题，我们可以解决许多任务。这些任务如下：

1. 查找连通分量

借助这个布尔矩阵问题，我们可以计算图中连接的组件数量。

2. 计算岛屿：

借助这个布尔矩阵问题，我们可以用真表示陆地，假表示水。完成此操作后，我们可以计算岛屿的数量。

3. 布尔矩阵乘法

正如我们所知，如果我们将两个布尔矩阵相乘，则结果矩阵将是一个布尔矩阵。在该结果矩阵中，真表示逻辑 AND 运算。

4. 在网格中寻找路径

借助这个布尔矩阵问题，我们可以找到从一个点到另一个点的可能路径数量。

5. 优化布尔矩阵操作

借助这个布尔矩阵问题，我们可以执行行约简、列约简或查找矩阵秩等操作。

在这个问题中，我们给定一个布尔矩阵。布尔矩阵的大小为 m X n。在这种方法中，我们必须修改矩阵单元格 mat[i][j]，使得如果矩阵值为 1（或真），则将第 i 行和第 j 列的所有单元格都设为 1。

让我们通过一个例子来理解这一点

示例

输入 {{1, 0},

{0, 0}}

输出 {{1, 1}

{1, 0}}

输入 {{0, 0, 0},

{0, 0, 1}}

输出 {{0, 0, 1},

{1, 1, 1}}

输入 {{1, 0, 0, 1},

{0, 0, 1, 0},

{0, 0, 0, 0}}

输出 {{1, 1, 1, 1},

{1, 1, 1, 1},

{1, 0, 1, 1}}

使用暴力解决布尔矩阵问题

方法：使用暴力

假设我们有一个包含所有非负数的矩阵。然后，我们必须遍历整个矩阵；如果找到元素 1，则必须将其所在列和行的所有元素更改为 -1，除了元素本身为 1 的情况。现在，我们必须再次遍历矩阵，如果元素是 -1，则将其更改为 1，这将是答案。

让我们使用编程语言来实现这种方法。

C++ 中的实现

输出

说明

在上面的代码中，我们创建了一个 setzero() 方法。此方法再次遍历矩阵，如果元素是 -1，则将其更改为 1 并返回我们的答案。我们借助 C++ 语言实现了此逻辑。

Java 实现

输出

说明

在上面的代码中，我们创建了一个 setzero() 方法。此方法再次遍历矩阵，如果元素是 -1，则将其更改为 1 并返回我们的答案。我们借助 Java 语言实现了此逻辑。

时间复杂度

上述方法的时间复杂度为 O((N*M)*(N + M))。

空间复杂度

上述方法的时间复杂度为 O(1)。

解决布尔矩阵问题的另一种方法

还有另一种方法可以解决上述问题。要解决这个问题，我们必须遵循以下步骤：

• 首先，我们必须创建两个临时数组，row[M] 和 col[N]。然后，我们将这两个临时数组初始化为 0。
• 然后，我们必须遍历输入矩阵 mat[M][N]。如果发现条目 mat[i][j] 为真，则必须将标记 row[i] 和 col[j] 设置为真。
• 然后，我们必须再次遍历输入矩阵 mat[M][N]。然后我们必须检查 mat[i][j] 的每个条目的 row[i] 和 col[j] 的值。如果 row[i] 或 col[j] 为真，则必须将 mat[i][j] 标记为真。

让我们借助编程语言来解决这种方法。

C++ 中的实现

输出

说明

在上面的代码中，我们创建了两个临时数组，然后将这两个数组传递给 modifyArray() 方法。此方法根据我们的需要修改数组。修改数组后，我们将其打印出来。上述代码是借助 C++ 编程语言完成的。

Java 实现

输出

说明

在上面的代码中，我们创建了两个临时数组，然后将这两个数组传递给 modifyArray() 方法。此方法根据我们的需要修改数组。修改数组后，我们将其打印出来。上述代码是借助 Java 编程语言完成的。

时间复杂度

这种方法的时间复杂度为 O(M*N)。

空间复杂度

这种方法的空间复杂度为 O(M + N)。

使用 O(1) 空间的布尔矩阵问题

直观理解

我们可以使用矩阵的第一行和第一列来完成相同的工作，而不是使用两个临时数组。通过这种方法，我们必须降低此问题的空间复杂度。我们必须在第二次遍历数组之前计算第一行和第一列。如果这样做，那么当我们反向遍历数组时，它会影响其他元素。

方法

我们可以使用矩阵的第一行和第一列来完成相同的工作，而不是使用两个临时数组。然后，我们可以检查特定列或行是否具有值 1。matrix[0][0] 是重叠的。

让我们借助编程语言来看一下。

C++ 中的实现

代码

输出

说明

在上面的代码中，我们实现了与方法 2 相同的逻辑。但我们没有使用两个临时数组，而是使用第一行和第一列。这降低了空间复杂度。我们借助 C++ 语言实现了这一点。

Java 实现

代码

输出

说明

在上面的代码中，我们实现了与方法 2 相同的逻辑。但我们没有使用两个临时数组，而是使用第一行和第一列。这降低了空间复杂度。我们借助 Java 语言实现了这一点。

时间复杂度

这种方法的时间复杂度为 O(M*N)。

空间复杂度

这种方法的空间复杂度为 O(1)。