我在类里面得到了一项练习,需要以下内容:
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
with0<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) 却一事无成,我该如何实现呢?
最佳答案
如果您修剪递归的不相关分支,则可以改进分而治之的实现以满足所需的运行时间。
将当前数组分为两个子数组后,比较每个子数组的第一个和最后一个元素。如果两者都是负数并且第一个小于最后一个,则您可以确定该子数组中的所有元素都是负数,并且您不必对其进行递归调用(因为您知道它将为总和贡献 0)。
如果子数组中的所有元素均为正数,您也可以停止递归(也可以通过比较子数组的第一个和最后一个元素来验证) - 在这种情况下,您必须对该子数组的所有元素求和,因此没有必要继续递归。
关于java - 获取循环有序数组中所有正数的总和,时间复杂度为 O(Log N),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58218856/