我有一个不同数字的矩阵,我需要一个有效的算法来找到所有四元组(四个条目,其中每两个在同一行,每两个在同一列),其中所有四个数字都是正数。例如:
这里我们有一个像这样的四元组
很容易找到一个非有效的解决方案,但我需要一些有效的方法。我真的很感激任何想法!
如果这些是非稀疏矩阵,我认为你能做的最好的事情就是取行对的按位乘积,在那里你使用每个元素的“真实性”。我会稍微改变你的例子:
1 2 0 1
1 1 0 0
0 1 1 1
这三款产品将
1*2 T T F F
1*3 T F T F
2*3 F T F F
如果您有一个 N*M 矩阵,其中 M 在硬件矩阵指令的线性处理能力范围内,那么这是一个快速的 N^2 算法。
现在,任何具有至少两个T
值的结果都表示一个四边形;您可以在 K^2 时间内生成所有坐标,其中 K 是T
直线中s的数量。
不幸的是,密集的数组会产生令人讨厌的 N^2 M^2 结果。但是,它易于处理、可维护,而且我认为它适用于半稀疏应用程序。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句