algorithm - 如何快速找到最大平均区间？

Question

从一个整数数组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) 更快的算法？或者我想知道是否存在随机方法。

Answer 1

有一个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 ，我们只需要找到一个区间[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) .

附言这种“平均问题”属于称为 fractional programming 的问题系列.类似的问题还有最小平均权重生成树、最小平均权重循环等。

附言再次。 O(logC)是一个宽松的界限。我认为我们可以通过一些仔细的分析来减少它。