从一个整数数组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)吗？或者我想知道是否存在一种随机方法。
问问题
1457 次
1 回答
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，我们只需要找到一个区间[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 这种“平均问题”属于称为分数规划的问题家族。类似的问题还有最小平均加权生成树、最小平均加权循环等。
再说一遍。这O(logC)是一个松散的界限。我认为我们可以通过一些仔细的分析来减少它。
于 2012-08-26T13:08:19.077 回答