平均值大于或等于k的最长连续子数组

Question

平均值大于或等于k的最长连续子数组

algorithmarray-algorithms

4

考虑一个包含N个整数的数组。寻找其元素平均值大于或等于给定数字k的最长连续子数组。

显然的解法时间复杂度为O(n^2)，我们能不能做得更好呢？

- Felix_Borja

2个回答

1

我们可以在O(n)时间和O(n)空间复杂度内解决问题：
我已经尝试了朴素方法和最优方法。
简而言之，该问题涉及两个步骤：
（1）从每个ar[i]中减去k，并在新数组中找到累积值。让我们称新数组为cumArr[]。
（2）现在问题变成在CumArr []中查找max（j-1），使得j> i且cumArr [j]> cumArr [i]。这一步是一个著名的问题，可以在许多地方找到。

以下是详细的运行代码： http://codeshare.io/Y1Xc8

可能会有一些小的边角情况，但很容易处理。
让我知道你们的想法。

- SHAN

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jma127 · Accepted Answer

我们可以通过在O（n）时间内从所有值中减去k，将此问题简化为具有总和>= 0的最长连续子数组。现在让我们计算前缀和：

index    0     1     2     3     4     5     6
array          2     -3    3     2     0     -1
prefix   0     2     -1    2     5     5     4

现在问题是找到距离最远的两个索引使得 prefix_right - prefix_left >= 0。让我们创建一个新的前缀-索引数组，并按照前缀和索引排序。

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5

我们可以进行从右到左的扫描，为每个前缀计算具有大于或等于当前前缀的最大索引：

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5
maxind   6     6     6     6     6     5     5

现在，让我们回到原始的前缀数组。对于每个前缀索引对，我们在新数组上执行二分查找，以找到最小的前缀 >= 当前前缀。从二分搜索前缀的maxind中减去当前前缀的索引，以检索从当前索引开始的最佳可能序列长度。选择具有最大长度的序列。

由于排序和n次二进制搜索，该算法的时间复杂度为O(n log n)。