0

我想询问为给定数组查找连续子数组的 FAST 方法。请注意，我不是在寻找最大和连续子数组，而是想对获得的子数组执行其他操作。我已经知道以下算法，但我正在寻找更有效的算法，因为这个算法的时间复杂度很差。

// N = number of elements in array A.
void subarr(int N, int A[]) {
  for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
      for (int k = j; k < N; k++) {
        cout << A[k] << ' ';
      }
      cout << endl;
    }
  }
}
4

1 回答 1

0

正如其他人在评论中指出的那样，您的示例不正确。它应该读作类似

for (int i = 0; i < N; i++) {
   for (int j = N-1; j >= i; j--) {
      for (int k=i; k<=j; k++) {
         cout << "A[" << k << "] ";
     }
     cout << endl;
   }
}

请注意，我将输出更改为仅按字面打印A[k]。这将只打印每个子数组一次。

至于您的问题，正如其他人所指出的那样，该算法将每个子数组打印一次，无需任何额外工作。我不相信你可以节省运行时间，因为这几乎是你要做的最少的工作。您确实从三个嵌套循环中获得了一些开销，但您可能需要全部三个：例如，子数组由

  1. 它的起点
  2. 它的终点或长度

你必须打印/剪掉中间的内容，从而产生第三个循环。

于 2015-08-10T10:12:40.337 回答