这是一个非常著名的跨国公司问我的问题。问题如下...
输入一个由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
// 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;
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个1。但是，RLE输出必须在每一行中重复此模式，导致O(n^2)的输出。
由于需要检查矩阵的每个条目，因此最坏情况始终是N * N。
通过额外使用小的2 * N存储空间，您可以在O（N * N）中执行操作。只需为每行创建一个掩码，为每列创建另一个掩码-扫描数组并在进行时更新掩码。然后再次扫描以根据掩码填充结果矩阵。
如果您正在执行输入矩阵正在更改的操作，则可以为输入的每行和列存储非零条目的计数（而不是简单的掩码）。然后，当输入中的条目更改时，相应地更新计数。在那时，我会完全放弃输出矩阵，并直接查询掩码/计数，而不是甚至维护输出矩阵（如果您确实想保留它，则可以在小于N * N的时间内更新它）。因此，加载初始矩阵仍将是O（N * N），但更新可以更少。
你说：
我们应该得到以下输出...
因此，您需要输出完整的矩阵，它具有N^2个元素。这是O(N*N)。
问题本身不是O(N*N)：您不必计算和存储整个矩阵：您只需要两个大小为N的向量L和C：
L[x]为1表示第x行是由1组成的行，否则为0；
C[x]为1表示第x列是由1组成的列，否则为0；
您可以在O(N)中构造这些向量，因为初始矩阵是稀疏的；您的输入数据将不是矩阵，而是包含每个非零元素的坐标（行、列）的列表。在读取此列表时，您设置L[line]=1和C[column]=1，问题就解决了：如果L[l]==1或C[c]==1，则M[l,c]==1。
大家好，
感谢mb14的评论，我认为我可以在少于O(NN)的时间内解决它... 最坏情况下需要O(NN)...
实际上，我们有一个给定的数组，假设
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
这里显然有高达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)个位不设为一（在这个5x5的情况下是20）。
相反地，您可以提出一个算法，总是以O(N^2)的时间完成：沿着顶部行和列求和，如果行或列得到非零答案，则填充整个行或列；然后解决较小的（N-1)x(N-1)问题。
所以存在至少需要N^2时间的情况，并且任何情况都可以在N^2时间内解决，而不需要额外的空间。
#include<stdio.h>
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();
}
这个程序只使用了2 4个临时变量（var1，var2，i和j），因此在时间复杂度为O(n^2)的情况下以恒定的空间运行。我认为不可能以小于O(n^2)的时间复杂度解决这个问题。
这取决于你的数据结构。
对于行，只有两种可能情况：
因此，结果可以被紧凑地表示为对行的引用数组。由于我们只需要两行，结果也只消耗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]]
O(n)个非零元素的矩阵。 - Phil Miller