矩阵有一列全部为“true”。如何在小于 O(mn) 的时间内找到它？

Question

我有一个真/假值的二维数组。我知道它有一些列的所有值都为 true，并且我知道它有一些行的所有值都为 false，除了与该列相交的位置。例如：

    0 1 2 3
  +--------
0 | N Y Y Y
1 | N Y Y Y
2 | N Y Y Y
3 | N N Y N
4 | N Y Y Y

我想找到所有值为 true 的列。有没有办法在不到O ( mn ) 的时间内做到这一点？

Answer 1

我们将包含所有 Y 的列称为“特殊”列，对于包含一个 Y 和其余 N 的第一行也是如此。

\n

从左上角开始。每当您看到 N 时，您就知道这不是特殊列，因此向右移动。每当您看到 Y 时，您就知道这是特殊列，或者不是特殊行，因此向下移动。当你一直走到底部的Y时，你一定已经穿过了特殊行，所以你知道你一定在特殊列中（因为只有特殊列才能让你穿过特殊行，并且一旦你在特殊的专栏上，你永远不会离开它）。

\n

这需要O ( m + n ) 时间，因为你最多向右移动n \xe2\x88\x921 次，向下移动最多m \xe2\x88\x921 次。

\n