2

我想在矩阵中找到一组连续的单元格。

例如，让我们考虑下面的二维矩阵。

二维二进制矩阵

在给定的矩阵中，有 2 组连续的单元格，其值为1：

二进制矩阵中的连续 1

这是查找这些组的一种方法：

  1. 为值为 1 的第一个单元格分配一个不同的值：假设A. 然后检查具有1相邻A值的单元格，并将这些单元格中的值设置为A。以这种方式搜索，直到找不到更多连续的单元格。

  2. 在下一步中递增A到B并从具有 value 的单元格开始1。然后按照与上述相同的步骤进行操作。

这是一种蛮力，在 3D 中不会有效。有谁知道我可以通过一些调整使用的任何算法？

或者有什么简单的方法可以解决这个问题？

4

3 回答 3

5

您正在尝试做的事情通常在标签connected component labeling下进行。我不会进一步详细说明，维基百科的文章比我能够或愿意更好地解释问题。

但是在我回答的时候...

您和 SO 上的许多其他人似乎认为对数组的所有元素进行简单的迭代（您用贬义词brute-force来表征）是不惜一切代价避免的事情。现代计算机非常非常快。按顺序访问数组的每个元素是大多数编译器可以优化的东西。

您似乎陷入了认为访问 3D 数组的每个元素都具有时间复杂度的陷阱O(n^3)，其中n是数组每个维度上的元素数。它不是：访问数组的元素是数组O(n)中n元素的数量。

即使访问数组中每个元素的时间复杂度在O(n^3)许多提供更好渐近时间复杂度的复杂算法中，在实践中也将证明提供比更简单算法更差的性能。许多复杂的算法使编译器更难优化代码。而且，请记住，这O(n^2)是算法的等价类，其中包括具有真实时间复杂度的算法，例如和O(m+k*n^2)都是常量mk

于 2012-07-31T09:50:46.373 回答
3

这是一个简单的洪水填充算法的一些伪代码：

>>> def flood(i, j, matrix):
...     if 0 <= i < len(matrix) and 0 <= j < len(matrix):
...         if matrix[i][j] == 1:
...             matrix[i][j] = 0
...             for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
...                 flood(i + dx, j + dy, matrix)

>>> count = 0
>>> while True:
...     i, j = get_one(matrix)
...     if i and j: #found a one
...         count += 1
...         flood(i, j, matrix)
于 2012-07-31T12:05:06.320 回答
0

这就像在图中找到强连接的组件一样，但是将整个事物扩展到 3 维。因此，您可以将任何线性时间算法用于 2D 图，并将 DFS 也用于 3 维。这应该是直截了当的。

由于这些算法是线性时间的，因此在运行时间复杂度方面您无法变得更好。

于 2012-07-31T09:50:50.133 回答