获取循环有序数组中所有正数的总和，时间复杂度为 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) 的建议是直接比较以满足两个标准中的第二个：最后一项小于第一项。 return vector[0] >= vector[iN-1]

如果你想要更复杂的东西，我忘记了算法名称，但你可以在中间点获取数组，并从那里进行两次有序搜索：从中间到开始，然后从中间到结束