c++ - 如何找到满足特定属性的各种长度的连续序列的数量？

Question

我有一个数组 A[] 有 N 个正整数元素.我必须找到满足特定属性的长度为 1,2,3,..,N 的序列数？我构建了一个复杂度为 O(nlogn) 的区间树。现在我想统计满足某个属性的序列数？

问题所需的所有属性都与序列之和有关

注意一个数组将有 N*(N+1)/2 个序列。我如何在 O(nlogn) 或 O(n) 中迭代所有这些？

Answer 1

如果我们让 k 是从 0 到 N(元素)的移动索引，我们将运行一个算法，该算法本质上是寻找满足条件(假设为 I)的 MIN R，然后 L = k 的每个其他子集也满足 R >= I(这是你的短路)。找到 I 后，只需返回 (L=k, R>=I) 的输出。这当然假设您的集合中的所有数字都是 >= 0。

要找到 I，对于每个 k，从元素 k + (N-k)/2 开始。弄清楚这个来自 (L=k, R=k+(N-k)/2) 的定义子集是否满足您的条件。如果是这样，则递减 R 直到不满足您的条件，然后 R=1 是您的 MIN(您可以选择打印这些结果，但在这些情况下它们的结果基本上会向后打印)。如果 (L=k, R=k+(N-k)/2) 不满足您的条件，则递增 R 直到它满足，这将成为您对 L=k 的 MIN。这会使每个 L=k 的搜索空间降低 2 倍。随着 k 增加并接近 N，您的搜索空间会不断减小。

// This declaration wont work unless N is either a constant or MACRO defined above
unsigned int myVals[N];
unsigned int Ndiv2 = N / 2;
unsigned int R;

for(unsigned int k; k < N; k++){

    if(TRUE == TESTVALS(myVals, k, Ndiv2)){ // It Passes
        for(I = NDiv2; I>=k; I--){
            if(FALSE == TESTVALS(myVals, k, I)){
                I++;
                break;
            } 
        }
    }else{                                  // It Didnt Pass
        for(I = NDiv2; I>=k; I++){
            if(TRUE == TESTVALS(myVals, k, I)){
                break;
            } 
        }
    }

    // PRINT ALL PAIRS from L=k, from R=I to R=N-1


    if((k & 0x00000001) == 0) Ndiv2++;

} // END --> for(unsigned int k; k < N; k++)

上面算法的复杂度是O(N^2)。这是因为对于 N 中的每个 k(即 N 次迭代/测试)，每个需要测试的值不超过 N/2。大 O 符号不关心 N/2，也不关心 N 随着 k 的增长而变小的事实，它只关心总大小。因此它会说 N 测试每 N 个值因此 O(N^2)

有一种替代方法会更快。这种方法是，每当您希望在次要(内部)for 循环内移动时，您都可以执行具有距离算法的移动。这将使您进入 O(nlogn) 组步骤。对于 N 中的每个 k(都必须进行测试)，您运行这种半距离方法以在 logN 时间内找到您的 MIN R 值。例如，假设您有一个包含 1000 个元素的数组。当 k = 0 时，我们基本上开始在索引 500 处搜索 MIN R。如果测试通过，而不是从 500 线性向下移动到 0，我们测试 250。假设 k = 0 的实际 MIN R 是 300。然后找到 MIN R 的测试如下所示:

R=500R=250R=375R=312R=280R=296R=304R=300

虽然这过于简单化，但您很可能需要优化并测试 301 和 299 以确保您处于最佳状态。另一个注意事项是，当您必须连续多次向同一方向移动时，除以 2 时要小心。