9

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

输入 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 左右。但我无法得到一个正确的想法。

4

13 回答 13

8

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

于 2010-09-07T14:31:00.990 回答
6

我想你可以优化它以获得最好的情况，但我想说你最坏的情况仍然是 O(N*N)：你最坏的情况将是一个全 0 的数组，你将不得不检查每一个元素。

优化将涉及在您找到“1”后立即跳过行或列（我可以提供详细信息，但您说您不关心 O(N*N)”，但除非您有元数据表明整行/列是空的，或者除非您有 SIMD 样式的方式来一次检查多个字段（例如，如果每行对齐 4，并且您可以读取 32 位的数据，或者您的数据是位掩码），您将始终必须处理全零数组的问题。

于 2010-09-07T14:31:09.370 回答
6

显然，输出矩阵及其否定版本也不必是稀疏的（取一个矩阵，将第一行的一半设置为 1，将其他任何内容设置为 0），因此时间取决于您被允许用于输出的格式. （我假设输入是元素列表或等价的东西，否则你无法利用矩阵稀疏的优势。）

O(M+N) 空间和时间的简单解决方案（M 是输入矩阵中 1 的数量）：取两个长度为 N 的数组，用 1 填充，遍历输入中的所有 1，并为每个删除 X来自第一个数组的坐标和来自第二个数组的 Y。输出是两个数组，它们清楚地定义了结果矩阵：当第一个数组的 X 坐标和第二个数组的 Y 坐标为 0 时，它的 (X,Y) 坐标为 0。

更新：根据语言，您可以使用一些技巧通过多次引用同一行来返回正常的二维数组。例如在 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;

当然，这只是一个普通数组，只要您不尝试编写它即可。

于 2010-09-07T15:21:44.077 回答
3

由于必须检查矩阵的每个条目，因此最坏的情况总是 N*N。

使用一个小的 2*N 额外存储，您可以在 O(N*N) 中执行操作。只需为每一行创建一个掩码，为每列创建一个掩码 - 扫描数组并随时更新掩码。然后再次扫描以根据掩码填充结果矩阵。

如果您正在做一些输入矩阵发生变化的事情，您可以为输入的每一行和每一列存储非零条目的计数（而不是简单的掩码）。然后，当输入中的条目发生更改时，您会相应地更新计数。那时，我将完全删除输出矩阵并直接查询掩码/计数，而不是维护输出矩阵（如果您真的想保留它，也可以在小于 N N 时间的情况下更新它）。所以加载初始矩阵仍然是 O(N N) 但更新可能要少得多。

于 2010-09-07T14:47:49.750 回答
3

输入矩阵可能是稀疏的，但除非您可以以稀疏格式（即(i,j)最初设置的对列表）获取它，否则仅读取您的输入将消耗 Ω(n^2) 时间。即使输入稀疏，也很容易得到 O(n^2) 输出来写入。作为一个骗子，如果你被允许输出一组设置行和设置列的列表，那么你可以降低到线性时间。当您的算法实际上必须产生比“是”或“否”更重要的结果时，就没有魔法了。

Mcdowella 对另一个答案的评论提出了另一种替代输入格式：游程编码。对于稀疏输入，读取它显然需要不超过 O(n) 的时间（考虑在 0 和 1 之间有多少个转换）。然而，从那里它崩溃了。考虑如下结构的输入矩阵：

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . . . 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . .
.     .
.       .
.         .

也就是说，在第一行交替使用 0 和 1，其他地方交替使用 0。显然是稀疏的，因为n/2总共有。但是，RLE 输出必须在每一行中重复此模式，导致 O(n^2) 输出。

于 2010-09-07T14:55:29.950 回答
2

你说：

我们应该得到输出...

所以你需要输出整个矩阵，它有 N^2 个元素。这是 O(N*N)。

问题本身不是 O(N*N)：您不必计算和存储整个矩阵：您只需要两个向量 L 和 C，每个向量的大小为 N：

如果行 x 是一行 1，则 L[x] 为 1，否则为 0；

如果行 x 是一行 1，则 C[x] 为 1，否则为 0；

您可以在 O(N) 中构造这些向量，因为初始矩阵是稀疏的；您的输入数据将不是矩阵，而是包含每个非零元素的坐标（行，列）的列表。在阅读此列表时，您设置 L[line]=1 和 C[column]=1，问题就解决了： M[l,c] == 1 if L[l]==1 OR C[c]= =1

于 2010-09-07T15:03:51.767 回答
2

嗨，伙计们，

感谢 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[row-array values][column array value] 给出了这些点......

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

我为几个数组做了这个并得到了所有数组的结果...... :)

如果我在任何地方错了，请纠正我...

感谢您的所有评论，伙计们...你们都非常乐于助人，而且我在此过程中确实学到了很多东西... :)

于 2010-09-08T14:08:29.450 回答
1

显然有O(N^2)工作要做。在矩阵中

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

所有位都必须设置为 1，而N*(N-1)不是设置为 1（在此 5x5 情况下为 20）。

相反，你可以想出一个总是及时完成的​​算法O(N^2)：沿最上面一行求和，让列，如果行或列得到非零答案，则填充整个行或列；然后解决较小的 (N-1)x(N-1) 问题。

所以存在至少必须采取的情况，N^2并且任何情况都可以在N^2没有额外空间的情况下解决。

于 2010-09-07T14:39:06.457 回答
0 
#include<stdio.h>

include

int main() { int arr[5][5] = { {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} }; int var1=0,var2=0,i,j;

for(i=0;i<5;i++)
   var1 = var1 | arr[0][i];

for(i=0;i<5;i++)
   var2 = var2 | arr[i][0];

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
      if(arr[i][j])
         arr[i][0] = arr[0][j] = 1;

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
          arr[i][j] = arr[i][0] | arr[0][j];

for(i=0;i<5;i++)
   arr[0][i] = var1;

for(i=0;i<5;i++)
   arr[i][0] = var2;

for(i=0;i<5;i++)
{
   printf("\n");             
   for(j=0;j<5;j++)
      printf("%d ",arr[i][j]);
}

getch();

}

This program makes use of only 2 4 temporary variables (var1,var2,i and j) and hence runs in constant space with time complexity O(n^2).. I Think it is not possible at all to solve this problem in < O(n^2).

于 2010-09-27T16:28:23.423 回答
0

检查值时不要填充矩阵的中心。当您浏览元素时，当您有 1 时，在第一行和第一列中设置相应的元素。然后回去填满。

编辑：实际上，这与安迪的相同。

于 2010-09-07T15:11:31.123 回答
0

这取决于您的数据结构。

行只有两种可能的情况：

  • 如果输入中有元素 (i,_)，则行 i 用 1 填充
  • 所有其他行都是相同的：即如果输入中有一个元素 (_,j)，则第 j 个元素为 1。

因此，结果可以紧凑地表示为对行的引用数组。由于我们只需要两行，因此结果也只会消耗 O(N) 内存。例如，这可以在 python 中实现如下：

def f(element_list, N):
  A = [1]*N
  B = [0]*N
  M = [B]*N
  for row, col in element_list:
    M[row] = A
    B[col] = 1
  return M

一个示例调用将是

 f([(1,1),(2,2),(4,3)],5)

结果

[[0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]

重要的一点是这里没有复制数组，即 M[row]=A 只是一个引用的赋值。因此复杂度为 O(N+M)，其中 M 是输入的长度。

于 2010-09-08T11:26:23.983 回答
0

如果您的矩阵是稀疏的，则复杂性在很大程度上取决于输入编码，尤其是在 NN 2或类似的东西中不能很好地测量，但就 N 而言，您的输入复杂度 M in 和输出复杂度 M out。我希望像 O(N + M in + M out ) 这样的东西，但很大程度上取决于编码和你可以使用它的技巧。

于 2010-09-07T14:55:38.310 回答
0

这完全取决于您的输入数据结构。如果您将矩阵（1s 和 0s）作为二维数组传递，则需要遍历它，即 O(N^2)。但是由于您的数据稀疏，如果您只传递 1 作为输入，您可以这样做，因此输出为 O(M)，其中 M 不是单元格的数量，而是 1 个单元格的数量。这将与此类似（下面的伪代码）：

列表 f(列表 l) {
   列出行_1；
   列出 cols_1；

    对于 l { 中的每个元素
        rows_1[elem.row] = 1;
        cols_1[elem.col] = 1;
    }

    列出结果；
    对于 rows_1 中的每一行 {
        对于 cols_1 中的每个列 {
             如果（行 == 1 || col == 1）{
                 添加（结果，new_elem（行，列））；
             }
        }
    }
   返回结果；
}
于 2010-09-07T15:01:55.517 回答