在3D二进制矩阵中查找连续单元组
use*_*700 2 algorithm 3d matrix
我想在矩阵中找到一组连续的单元格.
例如,让我们考虑下面的2D矩阵.
在给定的矩阵中,有两个连续的单元格组,其值为1:
以下是查找这些组的一种方法:
将值为1的第一个单元格指定为不同的值:让我们说
A.然后检查具有1相邻A值的单元格,并将这些单元格中的值设置为A.以这种方式搜索,直到找不到更多连续的单元格.在下一步中,
A增加到B并开始具有值的单元格1.然后按照上面的相同步骤操作.
这是一种蛮力,它在3D中效率不高.有没有人知道我可以使用一些调整的任何算法？
或者这个问题的任何简单解决方案？
您经常尝试做的是标签连接组件标签.我不会进一步详细说明,维基百科的文章比我能做的更好地解释了事情.
但是我正在回答......
你和许多其他人都认为,对于阵列的所有元素进行简单的迭代,你可以用贬义词蛮力来表征,这是不惜一切代价避免的.现代计算机非常非常快.按顺序访问数组的每个元素是大多数编译器可以优化地狱的东西.
你似乎陷入了这样的陷阱:认为访问3D数组的每个元素都具有时间复杂性O(n^3),其中n是数组中每个维度的元素数量.它不是:访问数组元素是在O(n)其中n为阵列中的元素的数量.
即使访问阵列中的每个元素的时间复杂度在O(n^3)许多提供更好的渐近时间复杂度的复杂算法中,实际上将证明比简单算法提供更差的性能.许多复杂的算法使编译器更难以优化代码.而且,请记住,这O(n^2)是一个等价类的算法,其中包括与真正的时间复杂度,如算法,O(m+k*n^2)其中两个m和k是常数