n×n二进制矩阵两行同置1检测：能否实现O(n²)或更优复杂度？

假设我们有一个n×n的二进制矩阵，例如：

[[0 1 0 1 0]
 [0 1 0 0 1]
 [1 0 1 1 1]
 [0 1 0 0 0]
 [0 1 0 0 0]]

我们可以轻松地以O(n³)的时间复杂度判断是否存在两行在至少两个相同列位置上均为1。上述示例中不存在这样的行对，而以下示例中存在：

[[1 0 1 1 1]
 [0 1 1 1 1]
 [0 0 1 1 1]
 [0 1 0 1 1]
 [1 1 1 0 0]]

该问题能否以O(n²)或比O(n³)更优的时间复杂度解决？

可以做到，而且能把时间复杂度优化到O(n²)，甚至在多数场景下更高效。具体思路如下：

方法一：基于列对的哈希检测 #

对于每一行，先提取出所有值为1的列的索引。然后生成该行中所有无序列对（比如列i和j，规定i<j避免重复），将这些列对存入哈希表。如果遍历过程中发现某个列对已经存在于哈希表中，说明存在两行共享这两个列的1，直接返回存在。

• 时间复杂度分析：假设每行平均有k个1，每行生成的列对数量为k*(k-1)/2。如果k远小于n，总时间会远低于O(n²)；若遇到每行全是1的极端情况，我们可以提前用鸽巢原理判断：当某行的1的数量k满足k*(k-1)/2 ≥ n时，n行的列对总数必然超过哈希表的容量，一定存在重复列对，这一步判断仅需O(n²)时间。

方法二：位运算+掩码哈希 #

将每一行转换为二进制数（或大整数）。对于当前行的二进制数row，我们枚举它所有1的列组合，生成仅保留两个1的掩码。检查这些掩码是否在哈希表中存在：如果存在，说明之前有行和当前行共享这两个列的1；如果不存在，就把这些掩码存入哈希表。

这种方法同样能将最坏时间复杂度控制在O(n²)，且在1的数量较少时效率更高。

总结 #

通过上述优化手段，我们可以把问题的时间复杂度降到O(n²)（最坏情况），在实际场景中通常能达到更优的性能。

内容的提问来源于stack exchange，提问作者Simd