- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
从一个整数数组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)
更快的算法?或者我想知道是否存在随机方法。
最佳答案
有一个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)
是一个宽松的界限。我认为我们可以通过一些仔细的分析来减少它。
关于algorithm - 如何快速找到最大平均区间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17642633/
我是一名优秀的程序员,十分优秀!