从整数数组中A[N],我想找到一个[i,j]具有最大平均值的区间(A[i] + A[i + 1] + .. + A[j]) / (j - i + 1).
间隔的长度(j - i + 1)应大于L.(L >= 1)
我想的是计算每个i~j的平均值,但这样做太慢了.(N太大了)
有比这更快的算法O(N^2)吗？或者我想知道是否存在随机方法.
RoB*_*oBa 10
有一种O(N*logC)算法,其中C与数组的最大元素值成比例.与近期论文中一些比较复杂的算法相比,该算法更易于理解,可以在短时间内实现,并且在实际中仍然足够快.
为简单起见,我们假设数组中至少有一个非负整数.
该算法基于二分搜索.首先,我们可以发现最终答案必须在范围内[0, max(A)],并且我们在每次迭代中将这个间隔减半,直到它足够小(例如10 -6).在每次迭代中,假设可用间隔是[a,b],我们需要检查最大平均值是否不小于(a+b)/2.如果是这样,我们得到一个较小的间隔[(a+b)/2, b],否则我们得到[a, (a+b)/2].
现在的问题是:给定一个数字K,如何检查最终答案至少K？
假设平均值至少K存在一些i,j这样的话(A[i] + A[i+1] + ... + A[j]) / (j - i + 1) >= K.我们将两边相乘(j-i+1),并将右边移动到左边,然后我们得到(A[i] - K) + (A[i+1] - K) + ... + (A[j] - K) >= 0.
所以,让B[i] = A[i] - K我们只需要找到一个interval [i, j](j - i + 1 > L)B[i] + ... + B[j] >= 0.现在的问题是:给定数组B和长度L,我们要找到一个长度大于的最大和的区间L.如果最大总和是>= 0,则原始平均数K是可能的.
第二个问题可以通过线性扫描来解决.让sumB[0] = 0,sumB[i] = B[1] + B[2] + ... + B[i].对于每个索引i,结束于的最大和间隔B[i]为sumB[i] - min(sumB[0], sumB[1], ..., sumB[i-L-1]).当逐渐扫描阵列时i,我们可以保持运行状态min(sumB[0], ..., sumB[i-L-1]).
子问题的时间复杂性是O(N).我们需要O(logC)迭代,因此总的复杂性是O(N*logC).
Ps这种"平均问题"属于称为分数编程的一系列问题.类似的问题是最小平均加权生成树,最小平均加权周期等.
Ps再次.这O(logC)是一个宽松的约束.我认为我们可以通过一些仔细的分析来减少它.