求O(Log N)中循环有序数组中所有正数的和。

Question

我在课堂上接受了一项要求如下的练习：

由N个整数构成的数组v是循环有序的，如果数组是有序的，或者是v[N‐1] ≤ v[0]和∃k与0<k<N (例如∀i≠k v[i] ≤ v[i+1] )。

示例：

给出一个循环有序的数组，其中包含多达10个正项，计算正值之和。对于最后一个例子，的答案是27。

我需要在java中使用Divide-and-Conquer方案来实现它，因为在最坏的情况下，复杂度是O(Log )，即数组大小的N。

到目前为止，我试图把一个值转到找到一个正值，然后知道其他的正值是相邻的，就有可能用O(1)复杂度将10个正值的最大值加起来。

我想做二进制搜索来实现O(Log )的复杂性，但这不会遵循分而治之的模式。

我很容易通过O(N)复杂度来实现它，如下所示：

public static int addPositives(int[] vector){

    return addPositives(vector,0,vector.length-1
}

public static int addPositives(int[] vector, int i0, int iN){
    int k = (i0+iN)/2;
    if (iN-i0 > 1){
        return addPositives(vector,i0,k) + addPositives(vector,k+1,iN);
    }else{
        int temp = 0;
        for (int i = i0; i <= iN; i++) {
            if (vector[i]>0) temp+=vector[i];
        }
        return temp;
    }
}

无论如何尝试登陆O(Log )，我都无法实现，我如何才能实现呢？

Answer 1

如果您修剪递归中不相关的分支，则可以改进分治实现，以满足所需的运行时间。

将当前数组划分为两个子数组后，比较每个子数组的第一个和最后一个元素。如果两者都是负值，而且第一个元素比最后一个元素都小，那么您肯定知道这个子数组中的所有元素都是负的，并且不需要对其进行递归调用(因为您知道它将占总数的0)。

如果子数组中的所有元素都是正的(也可以通过比较子数组的第一个和最后一个元素来验证)，您也可以停止递归--在这种情况下，您必须对该子数组的所有元素进行求和，因此没有必要继续递归。

Answer 2

我对O(Log )的建议是直接比较，以满足两个标准中的第二个:最后一项小于第一项。return vector[0] >= vector[iN-1]

如果你想要更复杂的东西，我忘了算法的名字，但是你可以在中间点得到数组，然后从那里进行两个有序的搜索:从中间到开始，然后从中间到结尾。