获取循环有序数组中所有正数的总和，时间复杂度为 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中使用分而治之的方案来实现它，因为最坏情况下的复杂性是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 贡献）总金额）。如果子数组中的所有元素都是正数，您也可以停止递归（也可以通过比较子数组的第一个和最后一个元素来验证） - 在这种情况下，您必须将该子数组的所有元素相加-array，所以没有必要继续递归。

Answer 2

我对 O(Log N) 的建议是直接比较以满足两个标准中的第二个：最后一项小于第一项。&nbsp;return vector[0] >= vector[iN-1]如果你想要更复杂的东西，我忘记了算法名称，但你可以在中间点获取数组，并从那里进行两次有序搜索：从中间到开始，然后从中间到结束