algorithm - 我们可以在小于 O(n*n) ...( nlogn 或 n) 的时间内计算吗

Question

这是一个非常非常著名的跨国公司问我的问题。问题如下……

输入一个由 0 和 1 组成的二维 N*N 数组。如果 A(i,j) = 1，则第 i 行第 j 列对应的所有值都将为 1。如果已经有 1，则保持为 1。

举个例子，如果我们有数组

  1 0 0 0 0 
  0 1 1 0 0 
  0 0 0 0 0 
  1 0 0 1 0
  0 0 0 0 0

我们应该得到输出为

 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 0
 1 1 1 1 1
 1 1 1 1 0

输入矩阵是稀疏填充的。

这可能在小于 O(N^2) 的情况下实现吗？

没有提供额外的空间是另一个条件。我想知道是否有办法使用空间 <= O(N) 来实现复杂性。

P.S:我不需要复杂度为 O(N*N) 的答案。这不是家庭作业问题。我已经尝试了很多，但找不到合适的解决方案，我想我可以在这里得到一些想法。为了复杂性，把打印放在一边

我的粗略想法是可以动态地消除遍历的元素数量，将它们限制在 2N 左右。但是我想不出一个正确的主意。

Answer 1

在最坏的情况下，您可能需要将 N * N - N 位从 0 切换为 1 以生成输出。看来您已经完全坚持使用 O(N*N)。