algorithm - 最小切片位置 - N 阶算法

Question

给定一个由 N 个整数组成的非空零索引数组 A。一对整数 (P, Q) 满足 0 ≤ P < Q < N，称为数组 A 的切片 (注意切片至少包含两个元素)。切片 (P, Q) 的平均值是 A[P] + A[P + 1] + ... + A[Q] 除以 切片的长度。准确地说，平均值等于 (A[P] + A[P + 1] + ... + A[Q])/(Q − P + 1)。

写一个函数:

解决方案(int A[], int N);

给定一个由 N 个整数组成的非空零索引数组 A，返回具有最小平均值的切片的起始位置。 如果有多个切片具有最小平均值，则应返回此类切片的最小起始位置。

假设:

N为[2..100,000]范围内的整数； 数组 A 的每个元素都是 [−10,000..10,000] 范围内的整数。 复杂性:

预期的最坏情况时间复杂度为 O(N)； 预期的最坏情况空间复杂度为 O(N)，超出输入存储空间(不包括输入参数所需的存储空间)。

你能只发布只有 N 阶的解决方案吗？

Answer 1

如果 A 只有正数，您可以这样处理:

pos = 0
min_avg = A[0] + A[1]
for (i=2; i<N; i++)
    m = A[i-1] + A[i]
    if (m < min_avg)
        min_avg = m
        pos = i-1
return pos

这只是对两个数字的切片取平均值，因为较大切片的平均值不可能小于较小切片的最小值。

如果 A 有负数，你可以先向上调整所有值:

offset = min(A)
for (i=0; i<N; i++)
    A[i] -= offset

结合前面的算法:

offset = min(A) * 2              (because we're adding two numbers below)
pos = 0
min_avg = A[0] + A[1] - offset
for (i=2; i<N; i++)
    m = A[i-1] + A[i] - offset
    if (m < min_avg)
        min_avg = m
        pos = i-1
return pos