重复移除最大平均子阵列
我有一个正整数数组。例如：
[1, 7, 8, 4, 2, 1, 4]
一个“约简操作”找到平均值最高的数组前缀，并将其删除。这里，数组前缀是指左端为数组开始的连续子数组，如上面的[1]或[1,7]或[1,7,8]。通过取较长的前缀来打破联系。
Original array: [ 1, 7, 8, 4, 2, 1, 4]
Prefix averages: [1.0, 4.0, 5.3, 5.0, 4.4, 3.8, 3.9]
-> Delete [1, 7, 8], with maximum average 5.3
-> New array -> [4, 2, 1, 4]
我将重复缩减操作，直到阵列为空：
[1, 7, 8, 4, 2, 1, 4]
^ ^
[4, 2, 1, 4]
^ ^
[2, 1, 4]
^ ^
[]
现在，实际上执行这些数组修改是没有必要的；我只是在寻找这个过程将删除的前缀长度列表，例如上面的[3,1,3]。
计算这些前缀长度的有效算法是什么？
最简单的方法是重新计算O（n^2）算法的每次迭代中的所有总和和平均值——我在下面附上了相关的Python代码。我正在寻找这种方法的任何改进——最好是O（n^2）以下的任何解决方案，但同样复杂但常数因子更好的算法也会有所帮助。
以下是我尝试过的一些事情（没有成功）：
这是一个朴素的二次方法的Python实现：
from fractions import Fraction
def find_array_reductions(nums: List[int]) -> List[int]:
"""Return list of lengths of max average prefix reductions."""
def max_prefix_avg(arr: List[int]) -> Tuple[float, int]:
"""Return value and length of max average prefix in arr."""
if len(arr) == 0:
return (-math.inf, 0)
best_length = 1
best_average = Fraction(0, 1)
running_sum = 0
for i, x in enumerate(arr, 1):
running_sum += x
new_average = Fraction(running_sum, i)
if new_average >= best_average:
best_average = new_average
best_length = i
return (float(best_average), best_length)
removed_lengths = []
total_removed = 0
while total_removed < len(nums):
_, new_removal = max_prefix_avg(nums[total_removed:])
removed_lengths.append(new_removal)
total_removed += new_removal
return removed_lengths
编辑：最初发布的代码出现了一个罕见的错误，使用Python的math进行了大量输入。isclose（）使用默认参数进行浮点比较，而不是正确的分数比较。这已在当前代码中修复。如果你好奇的话，可以在这个Try it online链接上找到一个错误的例子，以及一个前言，解释这个错误的确切原因。
共有2个答案
Matt和kcsquared的解决方案和一些基准的简化版本：
from itertools import accumulate, pairwise
def Matt_Pychoed(arr):
hull = [(0, 0)]
for x, y in enumerate(accumulate(arr), 1):
while len(hull) >= 2:
(x0, y0), (x1, y1) = hull[-2:]
dx0 = x1 - x0
dy0 = y1 - y0
dx1 = x - x1
dy1 = y - y1
if dy1*dx0 < dy0*dx1:
break
hull.pop()
hull.append((x, y))
return [q[0] - p[0] for p, q in pairwise(hull)]
from itertools import accumulate, count
from operator import truediv
def kc_Pychoed_2(nums):
removals = []
while nums:
averages = map(truediv, accumulate(nums), count(1))
remove = max(zip(averages, count(1)))[1]
removals.append(remove)
nums = nums[remove:]
return removals
使用20个不同的数组（10万个随机整数，从1到1000）进行基准测试：
min median mean max
65 ms 164 ms 159 ms 249 ms kc
38 ms 98 ms 92 ms 146 ms kc_Pychoed_1
58 ms 127 ms 120 ms 189 ms kc_Pychoed_2
134 ms 137 ms 138 ms 157 ms Matt
101 ms 102 ms 103 ms 111 ms Matt_Pychoed
其中，kc_Pychoed_1是kcsquared's，但带有整数运行_sum，没有数学。iClose。我验证了所有解对每个输入都计算相同的结果。
对于这样的随机数据，kcsquared似乎是O（n）。但如果数组严格递减，它将退化为二次型。对于arr=[1000999998，…，2，1]我得到了：
min median mean max
102 ms 106 ms 107 ms 116 ms kc
60 ms 61 ms 61 ms 62 ms kc_Pychoed_1
76 ms 77 ms 77 ms 86 ms kc_Pychoed_2
0 ms 1 ms 1 ms 1 ms Matt
0 ms 0 ms 0 ms 0 ms Matt_Pychoed
基准代码（在线试用！）：
from timeit import default_timer as timer
from statistics import mean, median
import random
from typing import List, Tuple
import math
from itertools import accumulate, count
from operator import truediv
def kc(nums: List[int]) -> List[int]:
"""Return list of lengths of max average prefix reductions."""
def max_prefix_avg(arr: List[int]) -> Tuple[float, int]:
"""Return value and length of max average prefix in arr"""
if len(arr) == 0:
return (-math.inf, 0)
best_length = 1
best_average = -math.inf
running_sum = 0.0
for i, x in enumerate(arr, 1):
running_sum += x
new_average = running_sum / i
if (new_average >= best_average
or math.isclose(new_average, best_average)):
best_average = new_average
best_length = i
return (best_average, best_length)
removed_lengths = []
total_removed = 0
while total_removed < len(nums):
_, new_removal = max_prefix_avg(nums[total_removed:])
removed_lengths.append(new_removal)
total_removed += new_removal
return removed_lengths
def kc_Pychoed_1(nums: List[int]) -> List[int]:
"""Return list of lengths of max average prefix reductions."""
def max_prefix_avg(arr: List[int]) -> Tuple[float, int]:
"""Return value and length of max average prefix in arr"""
if len(arr) == 0:
return (-math.inf, 0)
best_length = 1
best_average = -math.inf
running_sum = 0
for i, x in enumerate(arr, 1):
running_sum += x
new_average = running_sum / i
if new_average >= best_average:
best_average = new_average
best_length = i
return (best_average, best_length)
removed_lengths = []
total_removed = 0
while total_removed < len(nums):
_, new_removal = max_prefix_avg(nums[total_removed:])
removed_lengths.append(new_removal)
total_removed += new_removal
return removed_lengths
def kc_Pychoed_2(nums):
removals = []
while nums:
averages = map(truediv, accumulate(nums), count(1))
remove = max(zip(averages, count(1)))[1]
removals.append(remove)
nums = nums[remove:]
return removals
# Lengths of the segments in the upper convex hull
# of the cumulative sum graph
def Matt(arr):
if len(arr) < 2:
if len(arr) < 1:
return []
else:
return [1]
hull = [(0, 0),(1, arr[0])]
for x in range(2, len(arr)+1):
# this has x coordinate x-1
prevPoint = hull[len(hull) - 1]
# next point in cumulative sum
point = (x, prevPoint[1] + arr[x-1])
# remove points not on the convex hull
while len(hull) >= 2:
p0 = hull[len(hull)-2]
dx0 = prevPoint[0] - p0[0]
dy0 = prevPoint[1] - p0[1]
dx1 = x - prevPoint[0]
dy1 = point[1] - prevPoint[1]
if dy1*dx0 < dy0*dx1:
break
hull.pop()
prevPoint = p0
hull.append(point)
return [hull[i+1][0] - hull[i][0] for i in range(0, len(hull)-1)]
def pairwise(lst):
return zip(lst, lst[1:])
def Matt_Pychoed(arr):
hull = [(0, 0)]
for x, y in enumerate(accumulate(arr), 1):
while len(hull) >= 2:
(x0, y0), (x1, y1) = hull[-2:]
dx0 = x1 - x0
dy0 = y1 - y0
dx1 = x - x1
dy1 = y - y1
if dy1*dx0 < dy0*dx1:
break
hull.pop()
hull.append((x, y))
return [q[0] - p[0] for p, q in pairwise(hull)]
funcs = kc, kc_Pychoed_1, kc_Pychoed_2, Matt, Matt_Pychoed
stats = min, median, mean, max
tss = [[] for _ in funcs]
for r in range(1, 21):
print(f'After round {r}:')
arr = random.choices(range(1, 1001), k=100_000)
# arr = list(range(1000, 1, -1))
expect = None
print(*(f'{stat.__name__:^7}' for stat in stats))
for func, ts in zip(funcs, tss):
t0 = timer()
result = func(arr)
t1 = timer()
ts.append(t1 - t0)
if expect is None:
expect = result
assert result == expect
print(*('%3d ms ' % (stat(ts) * 1e3) for stat in stats), func.__name__)
print()
这个问题有一个有趣的O（n）解。
如果你画了一张累积和与指数的关系图，那么：
子数组中任意两个索引之间的平均值是图中这些点之间的直线的斜率。
第一个最高平均前缀将在从0到最大角度的点结束。下一个最高平均前缀必须有一个较小的平均值，并且它将在从第一个结尾到最大角度的点结束。继续到数组的结尾，我们发现...
这些平均值最高的分段正是累积和图的上凸包中的分段。
使用单调链算法找到这些段。由于点已经排序，因此需要O（n）时间。
# Lengths of the segments in the upper convex hull
# of the cumulative sum graph
def upperSumHullLengths(arr):
if len(arr) < 2:
if len(arr) < 1:
return []
else:
return [1]
hull = [(0, 0),(1, arr[0])]
for x in range(2, len(arr)+1):
# this has x coordinate x-1
prevPoint = hull[len(hull) - 1]
# next point in cumulative sum
point = (x, prevPoint[1] + arr[x-1])
# remove points not on the convex hull
while len(hull) >= 2:
p0 = hull[len(hull)-2]
dx0 = prevPoint[0] - p0[0]
dy0 = prevPoint[1] - p0[1]
dx1 = x - prevPoint[0]
dy1 = point[1] - prevPoint[1]
if dy1*dx0 < dy0*dx1:
break
hull.pop()
prevPoint = p0
hull.append(point)
return [hull[i+1][0] - hull[i][0] for i in range(0, len(hull)-1)]
print(upperSumHullLengths([ 1, 7, 8, 4, 2, 1, 4]))
印刷品：
[3, 1, 3]
-
我正在考虑这个leetcode问题，在完成这个天真的方法时遇到了一个问题。我在这里找到了一个最佳的解决方案。但我不确定我天真的尝试到底出了什么问题。 问题如下： 给定两个整数数组A和B，返回两个数组中出现的子数组的最大长度。 示例： 输入：A：[1,2,3,2,1]B：[3,2,1,4,7] 输出：3 说明：最大长度的重复子数组为[3,2,1]。 这是我当前的代码： 我的解决方案通过了几个测试用例
-
我必须解决一个很像最大子数组问题的问题。我必须找到平均值大于k的最大子数组。我以为下面这招。我可以将大小为n的数组a[]转换为B[]，其中B[I]=a[I]-K。所以现在平均值一定>0。但是平均值大于零并不意味着总和大于零？所以我可以直接应用Kadane的算法。我说的对吗？（总是在有1个正值的约束下）
-
你有一个整数数组。您必须找到子阵列的数量，该数量意味着（这些元素的总和除以这些元素的计数）舍入为零。我已经用O（n^2）时间解决了这个问题，但效率不够。有办法吗？
-
问题内容： 我试图显示最高平均工资；但是，我似乎无法使其正常工作。 我可以得到要显示的平均薪水清单： 但是，当我尝试显示具有以下项的最大平均薪水列表时： 它没有运行。我收到“无效标识符”错误。如何使用每个工人的平均工资来找到每个工人的最高平均工资？ 谢谢。 问题答案： 由聚合函数（例如avg）产生的列通常获得任意名称。只需为其使用别名，然后在其上进行选择：
-
在长度为N的数组中求和最大的邻接子数组。 输入格式： 输出格式： 返回一个整数，表示相邻子数组的最大可能和。 制约因素： 输入2:A=[-2,1,-3,4,-1,2,1,-5,4] 产出2：6 说明2：子数组[4,-1,2,1]的最大可能和为6。 你能告诉我为什么下面的代码不起作用，代码中的错误是什么吗：
-
所以，我刚刚进行了一次在线编程评估，给了我两个问题，其中一个是这个连续的子数组和提供了两个复杂的编码问题+8个MCQ，并将在1小时内完成。 这里我将讨论上面提到的子数组的最大邻接和之一。通常，我发现困难的部分是处理负数和连续。我所做的是首先将应用到给定的数组，然后再次按照负值的绝对值排序，就像i的例如，对于给定的随机数组，我在每个i和所有j迭代后都有一个max，如果max 。