最小切片位置N阶算法

Question

给出了一个由N个整数组成的非空零索引数组。一对整数（P，Q），如0≤ P

编写一个函数：

int解（int A[]，int N）；

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

假定：

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

预期最坏情况时间复杂度为O（N）；预计最坏情况下的空间复杂度为O（N），超出了输入存储空间（不计算输入参数所需的存储空间）。

你能只发布顺序N的解决方案吗？

Answer 1

    #include <assert.h>
    struct Slice { unsigned P, Q; };
    struct Slice MinSlice( int A[], unsigned N ) {
        assert( N>=2 );
        // find min slice of length 2
        unsigned P = 0;
        double min_sum = A[P] + A[P+1];
        for (unsigned i = 1; i < N-1; ++i)
            if ( min_sum > A[i] +A[i+1] ) {
                P = i;
                min_sum = A[P] + A[P+1];
            }
        unsigned Q = P+1;
        double min_avg = min_sum / 2;
        //extend the min slice if the avg can be reduced.
        //(in the direction that most reduces the avg)
        for (;;) {
            if ( P > 0 && ( Q >= N-1 || A[P-1] <= A[Q+1] ) ) {
                //reducing P might give the best reduction in avg
                double new_sum = A[P-1] + min_sum;
                double new_avg = new_sum / (Q - P + 2);
                if ( min_avg < new_avg )
                    break;
                min_sum = new_sum; 
                min_avg = new_avg; 
                --P;
             } else if ( Q < N-1 && ( P <= 0 || A[P-1] >= A[Q+1] ) ) {
                //increasing Q might give the best reduction in avg
                double new_sum = min_sum + A[Q+1];
                double new_avg = new_sum / (Q - P + 2);
                if ( min_avg < new_avg )
                    break;
                min_sum = new_sum; 
                min_avg = new_avg; 
                ++Q;
             } else
                 break;
        }
        struct Slice slice = { .P = P, .Q= Q };
        return slice;
    }

Answer 2

我想你是对的，我能做的最好的是一个O（N²）解决方案（这是Python的）：

from random import randint

N = 1000
A = [randint(-10000, 10000) for _ in xrange(N)]

def solution(A, N):
    min_avg = 10001
    for p in xrange(N):
        s = A[p]
        for q in xrange(1,N-p):
            s += A[p+q]
            a = s / (q+1.)
            if a < min_avg:
                min_avg = a
                pos = (p, q+1)
    return pos

print solution(A, N)

然而，较大切片的平均值趋向于原始范围的平均值（中间值）。在这种情况下，平均值为零，介于-10000和10000之间。大多数情况下，最小的平均值是两个值的一部分，但有时可能是三个值的一部分，很少可能是更多的值。所以我认为我之前的答案在大多数情况下都适用(

Answer 3

如果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