我们可以用小于O(n*n)...(nlogn或n)来计算它

Question

这是一个非常着名的跨国公司向我询问的问题.问题如下......

输入0和1的2D 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)来实现复杂性.

PS:我不需要给出O(N*N)复杂度的答案.这不是一个家庭作业问题.我已经尝试了很多,无法得到一个正确的解决方案,并认为我可以在这里得到一些想法.抛弃印刷的复杂性

我的粗略想法是可以动态地消除遍历的元素数量,将它们限制在2N左右.但我无法得到一个正确的想法.

Answer 1

在最坏的情况下,您可能需要将N*N - N位从0切换为1以生成输出.看起来你很好地坚持O(N*N).

Answer 2

我想你可以针对最好的情况对其进行优化,但是我很想说你的最坏情况仍然是O(N*N):你最糟糕的情况将是一个全0的数组,你将不得不检查每一个元素.

优化将涉及一旦找到"1"就跳过行或列(我可以提供详细信息,但您说您不关心O(N*N)",但除非您有元数据来指示整行/列是空的,或者除非你有SIMD风格的方法一次检查多个字段(例如,如果每行对齐4,你可以读取32位值数据,或者如果你的数据是一个位掩码),你将永远不得不处理一个全零数组的问题.

Answer 3

很明显,输出矩阵及其否定版本也不必稀疏(将第一行的一半设置为1的矩阵和其他任何设置为0的矩阵),所以时间取决于允许用于输出的格式.(我假设输入是一个元素列表或等价的东西,否则你无法利用稀疏的矩阵.)

O(M + N)空间和时间的简单解决方案(M是输入矩阵中的1的数量):取两个长度为N的数组填充1,迭代输入中的所有数组,并为每个数据删除X第一个数组的坐标和第二个数组的Y坐标.输出是两个数组,它们清楚地定义了结果矩阵:如果第一个数组的X坐标和第二个数据的Y坐标为0,则其(X,Y)坐标为0.

更新:根据语言,您可以使用一些技巧通过多次引用同一行来返回普通的2D数组.例如在PHP中:

// compute N-length arrays $X and $Y which have 1 at the column 
// and row positions which had no 1's in the input matrix
// this is O(M+N)
$result = array();
$row_one = array_fill(0,N,1);
for ($i=0; $i<N; $i++) {
    if ($Y[$i]) {
         $result[$i] = &$row_one;
    } else {
         $result[$i] = &$X;
    }
}
return $result;

当然这只是一个普通的数组,只要你不尝试写它.

Answer 4

嗨，伙计们，

感谢 mb14 的评论，我想我可以在不到 O(N N) 的时间内解决它...最坏的情况需要 O(N N)...

实际上，我们假设有给定的数组

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

让我们有 2 个大小为 N 的数组（这将是最坏的情况）...一个专门用于索引行和其他列...将 a[i][1] = 0 的数组放入一个数组中，然后将 a[1 ][j] =0 在另一个..

然后只取这些值并检查第二行和列...通过这种方式，我们得到只有 0 的行和列的值；完全...

行数组中的值的数量给出了结果数组中 0 的数量，点 a[行数组值][列数组值] 给出了这些点......

我们可以在 O(N N) 以下解决它，最坏的是 O(N N) ...正如我们所见，数组（大小为 N）减少 ....

我对几个数组执行了此操作，并得到了所有数组的结果......:)

如果我有什么错误的地方请纠正我...

感谢你们所有的评论...你们都非常有帮助，我一路上确实学到了很多东西...:)