arrays - Matrix 有一列全部为 'true' 。如何在不到 O(mn) 的时间内找到它？

Question

我有一个 true/false 值的二维数组。我知道它有一些列的所有值为 true，我知道它有一些行的所有值为 false except 它与该列相交。例如:

    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 时，您就知道这不是特殊列，所以向右移动。每当您看到 Y 时，您就知道这是特殊列，或者它不是特殊行，所以向下移动。当你一直走到底部的一个 Y 时，你一定已经穿过了特殊的行，所以你知道你必须在特殊的列中(因为只有特殊的列才能让你通过特殊的行，并且一次你在你永远不会离开的特殊专栏上)。

这需要 O(m+n) 时间，因为你最多向右移动 n-1次并最多向下移动 m-1 次。