1

这是给定 N 个数字的序列的后续问题，提取长度为 K 且范围小于 R 的序列的数量？

我基本上需要一个向量 v 作为大小 N 的答案，这样 V[i] 表示长度为 i 且范围 <=R 的序列数。

4

4 回答 4

1

传统上，在递归解决方案中，您将计算 K = 0、K = 1 的解决方案，然后在后续元素之间找到某种递归关系，以避免每次都从头开始重新计算解决方案。

然而在这里我相信也许从另一边攻击这个问题会很有趣，因为传播的属性：

给定一个扩展序列 R（或更少），任何子序列的扩展也低于 R

因此，我将首先建立一个从每个索引开始的散布 R 的最长子序列的列表。让我们称这个 list M，并知道M[i] = jwhere （原始序列）中j较高的索引where 。这将是 O(N)。SS[j] - S[i] <= R

现在，对于任何i，长度K从i或开始的序列数，这取决于是否大于0或不大于。一个简单的线性传递（从到）给了我们答案。这又是 O(N)。1KM[i] - iM0N-K

因此，如果我们调用V结果向量，V[k]表示长度为KinS且扩展低于的子序列的数量R，那么我们可以在 M 上的单次迭代中完成：

for i in [0, len(M)]:
    for k in [0, M[i] - i]:
        ++V[k]

该算法很简单，但是更新的数量可能相当令人生畏。在最坏的情况下，假设M[i] - i等于N - i，它是 O(N*N) 复杂度。您将需要一个更好的数据结构（可能是 Fenwick 树的改编版）来使用该算法以降低计算这些数字的成本。

于 2012-10-14T14:46:52.443 回答
0

如果您正在寻找连续序列，请尝试递归执行：范围小于 R 的 K 长度子序列集包含在 (K-1) 长度子序列集中。

在 K=0 时，您有 N 个解。每次增加 K 时，附加（resp. prepend）下一个（resp.previous）元素，检查它的范围是否低于 R，然后将其存储在一个集合中（查找重复项！）或丢弃它取决于结果。

如果认为该算法的复杂度在最坏情况下为 O(n*n)，但平均而言可能会更好。

于 2012-10-14T14:18:22.233 回答
0

从一个更简单的问题开始：计算序列的最大长度，从每个索引开始，范围等于 R。

为此，让 first 指针指向数组的第一个元素。增加第二个指针（也从数组的第一个元素开始），而指针之间的序列具有小于或等于 R 的范围。将由第二个指针传递的每个数组元素推送到 min-max-queue，由一对mix-max-stacks，在这个答案中描述。当 min-max-queue 报告的最大值和最小值之间的差异超过 R 时，停止增加第二个指针，递增V[ptr2-ptr1]，递增第一个指针（从 min-max-queue 中删除它所指向的元素），并继续增加第二个指针（控制范围）。

当第二个指针离开数组的边界时，V[N-ptr1]为所有剩余的 ptr1 递增（相应的范围可能小于或等于 R）。要添加小于 R 的所有其他范围，请计算数组 V[] 的累积和，从其末尾开始。

时间和空间复杂度都是 O(N)。

伪代码：

p1 = p2 = 0;
do {
  do {
    min_max_queue.push(a[p2]);
    ++p2;
  } while (p2 < N && min_max_queue.range() <= R);

  if (p2 < N) {
    ++v[p2 - p1 - 1];
    min_max_queue.pop();
    ++p1;
  }
} while (p2 < N);

for (i = 1; i <= N-p1; ++i) {
  ++v[i];
}

sum = 0;
for (j = N; j > 0; --j) {
  value = v[j];
  v[j] += sum;
  sum += value;
}
于 2012-10-14T14:46:49.280 回答
0

我认为在寻找所有具有扩展 R 的序列时，Matthieu 有正确的答案。

由于您只是在寻找长度为 K 的序列，因此您可以做得更好。与其查看从 i 开始的最大序列，不如查看从 i 开始的长度为 K 的序列，看看它是否具有范围 R。对每个 i 执行此操作，您将拥有所有长度为 K 且扩展为 R 的序列。

您不需要浏览整个列表，因为长度为 K 的序列的最新起点是 n-K+1。所以复杂度类似于 (n-K+1)*K = n*K - K*K + K。对于 K=1，这是 n，对于 K=n，它是 n。对于 K=n/2，它是 n*n/2 - n*n/4 + n/2 = n*n/2 + n/2，我认为这是最大值。所以虽然这仍然是 O(n*n)，但对于大多数 K 值，你会变得更好一些。

于 2012-10-14T16:56:53.953 回答