确定连续重复在二维阵列[C]

我有一个2维数组，它看起来像这样：确定连续重复在二维阵列[C]

我试图找出一种方法，以确定1的的最长连续链横跨或下降。在这种情况下，它从第4列第2行开始，它的长度是4，正在下降。

我想使用递归的，但我遇到一个0

时至今运行了一些问题跟踪的位置，特别是，我沿着这（东西线横跨只检查）：

main() { 
    ... 
    for(i = 0; i < n; i++) 
     for(j = 0; j < n; j++) 
     if (G[i][j] == 1) { 
      CheckAcross(i, j, n); 
     } 
    ... 
} 

void CheckAcross (int i, int j, int n) { 
    if (i < 0 || i >= n || j < 0 || j >= n) return; // outside of grid 
    if (G[i][j] == 0) return; //0 encountered 
    G[i][j] = WordCount + 1; 
    CheckAcross(i, j + 1, n); 

}

其中G[][]是包含1和0的，n是行/列的数目的2维阵列，i是行数和j是列号。

感谢您提前给予任何帮助！

来源

2011-05-12 Zach S

您当前的答案将需要O（n ）时间;评估一条线，你检查每个可能的开始和结束位置（每个可能的O（n）），并且有n条线。

您的算法是正确的，但让我们看看我们是否可以改善运行时间。

如果我们将问题分解为更简单的问题，即“这个1维数组中最长的1s连续链是什么？”，问题可能会变得更加简单。如果我们解决它2n次，那么我们有我们的答案，所以我们只需要得到这个小于O（n ）的改进。那么，我们可以简单地通过这条线，记住最长序列1的位置（开始和结束）和长度。这需要O（n）时间，并且是最优的（如果序列全部是1或0，我们将不得不读取每个元素以知道最长序列的开始/结束位置）。

然后，我们可以简单地解决这个问题，对于每一行和每一列，在O（n ）时间。

来源

2011-05-12 04:27:56 bdares

如果你想坚持自己的解决方案，你可以很容易地交换行和列，只需简单地交换索引，然后完成实现。 – bdares 2011-05-12 04:33:58

创建一个名为V的新的n×n矩阵。这将为每个单元存储该单元处的1的数量以及紧接其上的的数量。这将是O（n^2）。

checkAllVertical(int n) { 
    V = malloc(....) // create V, an n-by-n matrix initialized to zero 
    for(int r=0; r<n; r++) { 
     for(int c=0; c<n; c++) { 
     if(G[r][c]=1) { 
      if(r==0) 
      V[r][c] = 1; 
      else 
      V[r][c] = 1 + V[r][c]; 
     } 
     } 
    } 
}

你并不真的需要分配所有的V.一次一行就足够了。

来源

2011-05-14 18:59:57

确定连续重复在二维阵列[C]

回答

相关问题