java - 获取循环有序数组中所有正数的总和，时间复杂度为 O(Log N)

Question

我在类里面得到了一项练习，需要以下内容:

An array v formed by N integers is circularly ordered if, either the array is ordered, or else v[N‐1] ≤ v[0] and ∃k with 0<k<N such as ∀i≠k v[i] ≤ v[i+1].

Example:

Given a circularly ordered array with as much as 10 positive items, calculate the sum of the positive values. For this last example the answer would be 27.

我被要求在 java 中使用分治方案来实现它，因为最坏情况下的复杂性是O(Log N)，即 N 是数组大小。

到目前为止，我尝试旋转一个值，直到找到一个正值，然后知道其他正值是相邻的，就可以以 O(1) 的复杂度对最多 10 个正值求和。

我想过进行二分搜索来实现 O(Log N) 复杂度，但这不遵循分而治之的模式。

我可以轻松地通过 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 N) 却一事无成，我该如何实现呢？

Answer 1

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

将当前数组分为两个子数组后，比较每个子数组的第一个和最后一个元素。如果两者都是负数并且第一个小于最后一个，则您可以确定该子数组中的所有元素都是负数，并且您不必对其进行递归调用(因为您知道它将为总和贡献 0)。

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