2

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

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

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

4

2 回答 2

0

@user1907531：首先，如果您正在参加如此重要的国家级在线比赛，您应该避免使用这种廉价的技巧和方法来领先于其他应得的人。其次，像你这样的作弊者总是作弊者，但这一切都阻碍了那些提出问题的人和与你不同的竞争对手的辛勤工作。第三，如果@trumetlicks 问你为什么不把这些问题标记为作业，你会在那里撒另一个谎。最后，我不知道怎么会有这么多人回答这个作弊者在不知道出处/网站/的情况下提出的这个问题这个问题的来源。这肯定不能由任何印度学校的老师给家庭作业。告诉大家，这个作弊者在比赛结束前 6 小时向你询问了印度大学跑步比赛的完整解决方案，他肯定得到了很多直接的帮助，最重要的是，他邀请了 100 名其他人从这里给出的答案中作弊。所以，祝所有这些作弊者好运。

于 2013-02-02T12:48:35.753 回答
0

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

要找到 I，对于每个 k，从元素 k + (Nk)/2 开始。弄清楚 (L=k, R=k+(Nk)/2) 中定义的子集是否满足您的条件。如果是这样，则递减 R 直到不满足您的条件，然后 R=1 是您的 MIN（您可以选择随时打印这些结果，但在这些情况下它们的结果将基本上向后打印）。如果 (L=k, R=k+(Nk)/2) 不满足您的条件，则递增 R 直到满足，这将成为您的 L=k 的最小值。这会将每个 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。如果测试通过，我们将测试 250，而不是从 500 线性向下移动到 0。假设 k = 0 的实际 MIN R 为 300。然后查找 MIN R 的测试如下所示：

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

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

于 2013-02-01T13:40:01.143 回答