最小平均两片混合系数

Question

给出了一个由N个整数组成的非空零索引数组A。一对0（P <Q <N
<N）的整数（P，Q）称为数组A的切片（请注意，切片包含至少两个元素）。切片的平均值（P，Q）是A [P] + A [P +1] + … + A
[Q]的总和除以切片的长度。确切地说，平均值等于（A [P] + A [P + 1] + … + A [Q]）/（Q − P +1）。
例如，数组A这样：

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

包含以下示例切片：

• 切片（1，2），其平均值为（2 + 2）/ 2 = 2;
• 切片（3，4），其平均值为（5 +1）/ 2 = 3;
• 切片（1，4），其平均值为（2 + 2 + 5 +1）/ 4 = 2.5。

目的是找到平均值最小的切片的起始位置。

编写一个函数：

class Solution { public int solution(int[] A); }

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

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

如上所述，该函数应返回1。

假使，假设：

• N是在[2..100,000]范围内的整数；
• 数组A的每个元素都是[-10,000..10,000]范围内的整数。

复杂：

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

输入数组的元素可以修改。

这是我最好的解决方案，但显然在时间复杂度方面不是最佳的。
有任何想法吗？

public int solution(int[] A) {
    int result = 0;
    int N = A.length;
    int [] prefix = new int [N+1];
    for (int i = 1; i < prefix.length; i++) {
        prefix[i] = prefix[i-1] + A[i-1];
    }
    double avg = Double.MAX_VALUE;
    for (int i = 1; i < N; i++) {
        for (int j = i+1; j <=N; j++) {
            double temp = (double)(prefix[j]-prefix[i-1]) /(double)(j-i+1);
            if (temp < avg) {
                avg = temp;
                result = i-1;
            }
        }
    }
    return result;
}

https://codility.com/demo/results/demo65RNV5-T36/

Answer 1

我几天前发布了这个：

看一下这个：

http://codesays.com/2014/solution-to-min-avg-two-slice-by-
codility/

他们在那里详细解释了为什么他们的解决方案有效。我自己还没有实现它，但是我一定会尝试的。

希望能帮助到你！

但我刚刚看到它已被主持人删除。他们说链接无效，但我只是尝试了一下，效果很好。我再次发布它，希望可以验证该链接是否正确。

现在，我还可以根据之前提供的代码分析链接提供实现：https ://codility.com/demo/results/demoERJ4NR-
ETT/

class Solution {
    public int solution(int[] A) {
        int minAvgIdx=0;
        double minAvgVal=(A[0]+A[1])/2; //At least two elements in A.
        double currAvg;
        for(int i=0; i<A.length-2; i++){
            /**
             * We check first the two-element slice
             */
            currAvg = ((double)(A[i] + A[i+1]))/2;
            if(currAvg < minAvgVal){
                minAvgVal = currAvg;
                minAvgIdx = i;
            }
            /**
             * We check the three-element slice
             */
            currAvg = ((double)(A[i] + A[i+1] + A[i+2]))/3;
            if(currAvg < minAvgVal){
                minAvgVal = currAvg;
                minAvgIdx = i;
            }
        }
        /**
         * Now we have to check the remaining two elements of the array
         * Inside the for we checked ALL the three-element slices (the last one
         * began at A.length-3) and all but one two-element slice (the missing
         * one begins at A.length-2).
         */
        currAvg = ((double)(A[A.length-2] + A[A.length-1]))/2;
        if(currAvg < minAvgVal){
            minAvgVal = currAvg;
            minAvgIdx = A.length-2;
        }
        return minAvgIdx;
    }
}