0

我有一个看起来像这样的二维数组：

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

我试图找出一种方法来识别最长的连续链 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是行/列数，i是行号，j是列号。

感谢您提前提供任何帮助！

4

2 回答 2

0

创建一个名为 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-14T18:59:57.273 回答
0

您当前的答案将花费 O(n 3 ) 时间；要评估单行，您检查每个可能的开始和结束位置（每个可能的 O(n)），并且有 n 行。

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

如果我们把它分解成更简单的问题，问题可能会变得更简单，即“这个一维数组中最长的连续 1 链是什么？”。如果我们2n多次解决它，那么我们就有了答案，因此我们只需将其降低到小于 O(n 2 ) 即可进行改进。

好吧，我们可以简单地遍历这条线，记住最长的 1 序列的位置（开始和结束）和长度。这需要 O(n) 时间，并且是最优的（如果序列全是 1 或 0，我们必须读取每个元素才能知道最长序列的开始/结束在哪里）。

然后我们可以在 O(n 2 ) 时间内简单地解决每一行和每一列的问题。

于 2011-05-12T04:27:56.153 回答