algorithm - 在 3D 二进制矩阵中查找连续单元格组

Question

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

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

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

这是找到这些组的一种方法:

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

2. 在下一步中，将 A 递增到 B 并从值为 1 的单元格开始。然后按照与上述相同的步骤。

这是一种蛮力，在 3D 中效率不高。有谁知道我可以稍加调整就可以使用的算法吗？

或者这个问题有什么简单的解决方案吗？

Answer 1

您尝试执行的操作通常位于标签 connected component labelling 下.我不会进一步详细说明，维基百科文章解释的比我能或会更好。

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

您和 SO 上的许多其他人，似乎认为对数组的所有元素进行简单迭代(您用贬义词 蛮力 来描述)是完全应该避免的费用。现代计算机非常非常快。按顺序访问数组的每个元素是大多数编译器可以优化的事情。

您似乎陷入了这样一种陷阱，即认为访问 3D 数组的每个元素都具有 O(n^3) 的时间复杂度，其中 n 是数组每个维度上的元素数。事实并非如此:访问数组元素的时间复杂度为 O(n)，其中 n 是数组中元素的数量。

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