最小平均两层编码

Question

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

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

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

写一个函数：

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..100000]范围内的整数
• 数组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

棘手的部分是，即使在开始编码之前，也要弄清楚是否存在长度为2或3的平均最小切片。从这里开始会更容易，但我有几个重要的注意事项：

>

你根本不需要除法，你可以用乘法来代替，这样你就可以在长度为6的切片上得到相同的平均值，并且完全避免浮点运算

循环中不需要除法（在我的例子中是乘法），只要最后一次就足够了。

如果你真的必须这样做，你应该总是比较两个浮点数，比如：EPSILON=0.0000001（取决于你寻找的精度，这个数字可能是不同的数字）和Math。abs（平均2-3）

这是我用Java开发的解决方案，它的可编译性达到了100%：

public int solution(int[] A) {
    if (A.length == 2) return 0;

    int minSliceTwo = A[0] + A[1];
    int minTwoIndex = 0;

    int minSliceThree = Integer.MAX_VALUE;
    int minThreeIndex = 0;

    for (int i = 2; i < A.length; i++) {
        int sliceTwo = A[i - 1] + A[i];
        if (sliceTwo < minSliceTwo) {
            minSliceTwo = sliceTwo;
            minTwoIndex = i - 1;
        }

        int sliceThree = sliceTwo + A[i - 2];
        if (sliceThree < minSliceThree) {
            minSliceThree = sliceThree;
            minThreeIndex = i - 2;
        }
    }
    int averageMinTwo = minSliceTwo*3;
    int averageMinThree = minSliceThree*2;

    if (averageMinTwo == averageMinThree) return Math.min(minTwoIndex, minThreeIndex);
    else return averageMinTwo < averageMinThree ? minTwoIndex : minThreeIndex;
}

Answer 2

几天前我发了这个帖子：

看看这个：

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

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

希望有帮助！

但我刚刚看到它被一位版主删除了。他们说链接已经死了，但我刚试过，效果很好。我再次发布它，希望它能被证实链接是好的。

现在，我还可以提供我的实现，基于我之前提供的codesays链接：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;
    }
}

Answer 3

基于Kadane算法的C语言100%得分

int solution(vector<int> &A) {

    // Find prefix sum.
    int N = A.size();
    vector<int> ps(N + 1, 0);
    
    for (int i = 1; i <= N; i++) {
        ps[i] = A[i - 1] + ps[i - 1];
    }

    int lft_idx, min_lft_idx;
    double avg_here, min_avg, avg_of_two, avg_with_prev;
    
    // Initialize variables at the first possible slice (A[0:1]).
    lft_idx = min_lft_idx = 0;
    avg_here = min_avg = (A[0] + A[1]) / 2.0;
    
    // Find min average of every slice that ends at ith element,
    // starting at i = 2.
    for (int i = 2; i < N; i ++) {

        // average of A[lft_idx : i]
        avg_with_prev = ((double) ps[i + 1] - ps[lft_idx]) / 
                        (i - lft_idx + 1);

        // average of A[i - 1 : i]
        avg_of_two = (A[i - 1] + A[i]) / 2.0;
        
        // Find minimum and update lft_idx of slice
        // (previous lft_idx or i - 1).
        if (avg_of_two < avg_with_prev) {
            avg_here = avg_of_two;
            lft_idx = i - 1;
        }
        else
            avg_here = avg_with_prev;
        
        // Keep track of minimum so far and its left index.
        if (avg_here < min_avg) {
            min_avg = avg_here;
            min_lft_idx = lft_idx;
        }
    }
        
    return min_lft_idx;
}

我对2/3元素的子片解决方案不满意（拜托！在面试期间谁会想到这一点？），也没有解释（或缺乏解释），所以我继续寻找其他方法。然后我发现了关于卡丹的最大子阵问题（MSP）算法，这让我找到了一个不同的解决方案。

基本问题是（与MSP类似）：包含第i个元素的切片的最小平均值是多少？

为了回答这个问题，我们将寻找以第i个元素结尾的切片，只更新它们的左索引。也就是说，我们必须检查切片A[lft_idx： i]。

假设我们知道切片的lft_idxA[lft_idx： i-1]的最小平均值，那么我们有两种可能性：

1. A[lft_idx： i]的平均值最小。
2. A[i-1： i]的平均值是最小的（最短的可能切片有2个元素）。

在情况1中，我们继续增长从lft_idx开始的切片。

然而，在案例2中，我们发现增加前一个切片实际上会增加平均值。因此，我们重新开始，并将切片的开头（lft_idx）重置为前一个元素（i-1）。现在，我们有一个新的2号最佳切片从这一点增长。

最后，我们想要全局最小平均值，所以我们需要跟踪到目前为止的最小值以及它从哪里开始（问题只要求这样，但我们也可以保存正确的索引）。

注意：我在这里使用前缀和来计算切片平均值，因为这是Codibility中出现的问题，但它很容易被一个具有上一个切片大小的变量和另一个乘法替换。