0

对于仅具有 0 或 1 的给定矩阵 NxN。找出至少出现一个 1 的行数和列数。

例如

0 0 0 0

1 0 0 1

1 0 0 1

1 1 0 1

至少有一次为 1 的行数：3

Col 计数有 1 至少一次：3

头脑被冻结想不出比正常双循环更好的方法给我 O(n^2) 期待一些帮助

4

2 回答 2

1

该解决方案证明您不能读取小于 O(N^2) 的矩阵，但如果您对这个问题的意思是您想在搜索中计算您的结果：我认为这不是做它或说我需要比 O(2*(n^2)) 更好地解决这个问题。

您需要了解数组中的每个单元格。假设您有一个图表，每个顶点都指向矩阵中的一个单元格。要查找您应该在图表中搜索的单元格的值。您可以使用 DFS 来做到这一点。命令。

DFS的时间和空间分析根据其应用领域的不同而不同。在理论计算机科学中，DFS 通常用于遍历整个图，并且需要时间 O(|E|)，与图的大小成线性关系。在这些应用程序中，它还在最坏的情况下使用空间 O(|V|) 来存储当前搜索路径上的顶点堆栈以及已经访问过的顶点集。因此，在这种情况下，时间和空间界限与广度优先搜索相同，选择使用这两种算法中的哪一种较少取决于它们的复杂性，而更多地取决于两种算法产生的顶点排序的不同属性.

并且您的图形中有 N^2 个顶点 - 数组至少 (O(V+E) >= O(V))。所以你不能比使用每个数据结构的 O(n^2) 做得更好。（因为计算这个顺序与边缘结构无关）。

maxcol=0;
for(int i=0;i<n;i++)
{
  sumcol=0;
  for(int j=0;j<n;j++)
  {
    if (a[i][j]==1)
     {
       sumcol=sumcal+1;
     }  
  }
  if (sumcol>maxcol)
   {
     maxcol=sumcol;
   }
}

对行重复此操作。这是非常简单的解决方案，但此代码具有最小空间。您无法通过算法思想对其进行改进。您应该注意算法复杂性的方法。您可以通过一次搜索来解决它，但只会增加复杂性你的代码。

于 2013-03-18T21:05:47.710 回答
0

思路：将每行每列的数字总和存储在矩阵中。

附加存储：O(n * log(n)) - 假设 O(log(n)) 位存储一个数字。

计算非零行和列所需的时间：O(n)。

这是一种时间优化算法，而不是“空间和时间优化算法”——它需要更多空间但更少时间。

于 2013-03-19T00:41:35.753 回答