您能以多快的速度检测 n x n 二进制矩阵中的两行是否在公共位置上（至少）有两个位？

Question

假设我们有一个 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^3) 时间内确定是否有两行在公共位置（列）至少有两个 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^2) 时间内或比 O(n^3) 更快的时间内解决？

Answer 1

是的，您可以在 O(n²) 时间内完成此操作。

初始化一个全为零的 n x n 临时矩阵。

然后，对于每一行，迭代位置 (i,j) 处的每对 1，并检查矩阵中的每个位置 (i,j)。 如果包含 0，则在该位置写入行号 (1-n)。否则，您会在当前行和存储在 (i,j) 的行号之间找到一对匹配的 1。

显然，该算法对于单行可能需要 O(n²) 时间，但是在临时矩阵中只有 n² 位置需要填充，因此总运行时间被限制为 O(n ²）还有，