Java 最小平均两片 Codility

Min Average Two Slice Codility

提问by Jose P.

A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q ? P + 1).
For example, array A such that:

给出了一个由 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)。
例如，数组 A 使得：

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

contains the following example slices:

包含以下示例切片：

• slice (1, 2), whose average is (2 + 2) / 2 = 2;
• slice (3, 4), whose average is (5 + 1) / 2 = 3;
• slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

• 切片 (1, 2)，其平均值为 (2 + 2) / 2 = 2；
• 切片 (3, 4)，其平均值为 (5 + 1) / 2 = 3；
• 切片 (1, 4)，其平均值为 (2 + 2 + 5 + 1) / 4 = 2.5。

The goal is to find the starting position of a slice whose average is minimal.

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

Write a function:

写一个函数：

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

that, given a non-empty zero-indexed array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.
For example, given array A such that:

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

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

the function should return 1, as explained above.

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

Assume that:

假使，假设：

• N is an integer within the range [2..100,000];
• each element of array A is an integer within the range [?10,000..10,000].

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

Complexity:

复杂：

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

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

Elements of input arrays can be modified.

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

---

---

This is my best solution, but obviously not optimal in terms of time complexity.
Any ideas?

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

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/

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

采纳答案by cotupha

I had posted this some days ago:

前几天我发过这样的帖子：

Check this out:

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

In there, they explain with great detail why their solution works. I haven't implemented it myself yet, but I will definitely try it.

Hope it helps!

看一下这个：

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

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

希望能帮助到你！

but I just saw it was deleted by a moderator. They say the link is dead, but I just tried it and it works fine. I'm posting it once again, hoping it can be validated that the link is good.

但我刚看到它被版主删除了。他们说链接已失效，但我刚刚尝试过，效果很好。我再次发布它，希望可以验证链接是否正确。

And now I can also provide my implementation, based on the codesays link that I provided before: https://codility.com/demo/results/demoERJ4NR-ETT/

现在我还可以根据我之前提供的 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;
    }
}

回答by Alexander M.

My 100/100 score solution written in php http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html

我用 php 编写的 100/100 分数解决方案http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html

回答by hrajesh4u

My Answer with score 100

我的回答 100 分

public class MinAvgTwoSlice {

public static void main(String[] args) {

    System.out.println(new MinAvgTwoSlice().solution(new int[] {4, 2, 2, 5, 1, 5, 8} ));    
}

public int solution(int[] A) {

    double minAvg = 100000;
    int index=0;

    if(A.length<=2) {

        return 0;
    }

    for(int i=0;i<A.length-2;i++) {

        if((A[i]+A[i+1])/2.0<minAvg) {
            minAvg=(A[i]+A[i+1])/2.0;
            index=i;
        }

        if((A[i]+A[i+1]+A[i+2])/3.0<minAvg)  {

            minAvg=(A[i]+A[i+1]+A[i+2])/3.0;
            index=i;
        }
    }

    int aMax = A.length-2;

    if((A[aMax]+A[aMax+1])/2.0<minAvg) {

        minAvg=(A[aMax]+A[aMax+1])/2.0;
        index=aMax;
    }

    return index;
}
}

Thanks : Based on the logic provided in codesays.com

谢谢：基于 codesays.com 中提供的逻辑

回答by kangaroosterus

Here's a Prefix Sum implementation that works (100% in Codility):

这是一个有效的 Prefix Sum 实现（在 Codility 中为 100%）：

import sys

def solution(A):

    n             = len(A)
    pre_sum       = [0] * (n+1)
    min_slice_avg = sys.maxint
    min_slice_idx = 0

    for i in xrange(1,n+1):
        pre_sum[i] = pre_sum[i-1] + A[i-1]

        # calculate at least 2 prefix sums
        if i-2 < 0: continue

        # check prev 3 slices if we have calculated 3 prefix sums
        if i>=3:
            prev_3_slice_avg = (pre_sum[i] - pre_sum[i-3]) / 3.0

            if prev_3_slice_avg < min_slice_avg:
                min_slice_avg = prev_3_slice_avg
                min_slice_idx = i-3

        # check prev 2 slices
        prev_2_slice_avg = (pre_sum[i] - pre_sum[i-2]) / 2.0

        if prev_2_slice_avg <  min_slice_avg:
            min_slice_avg = prev_2_slice_avg
            min_slice_idx = i-2

    return min_slice_idx

回答by usermark8

I understand that http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.htmlprovides best explanation and solution that I know so far. Since this is under the prefix sum section, the following is the one I tried to get familiar with the prefix sum method.

我知道http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html提供了迄今为止我所知道的最佳解释和解决方案。由于这是在前缀和部分下，下面是我尝试熟悉前缀和方法的部分。

function solution($A) {
        // write your code in PHP5.3

        $N = count($A);
        if ($N > 100000 || $N < 2 ) {
            return -1;
        } elseif ($N === 2) {
            return 0;
        }

        $presum = array();
        $presum[] = 0;

        $mavg = PHP_INT_MAX;

        $index = 0;
        for ($i = 0; $i < $N; $i++) {                
            $presum[$i+1] = $A[$i] + $presum[$i];
        }

        for ($i = 0; $i < $N-2; $i++) {
            for ($j = $i+1; $j < $i + 3; $j++ ) {
                $avg = ($presum[$j+1] - $presum[$i]) / ($j - $i + 1);

                if ($mavg > $avg) {
                    $mavg = $avg;
                    $index = $i;
                }
            }
        }
        $avg = ($presum[$N] - $presum[$N-2]) / 2;
        if ($mavg > $avg) {
            $index = $N - 2;
        }

        return $index;
}

回答by Andrey Petrov

The tricky part is to figure out even before you start coding that there is for sure an average min slice of length 2 or 3. From there it is easier, but I have a few important notes:

棘手的部分是在你开始编码之前弄清楚肯定有一个长度为 2 或 3 的平均最小切片。 从那里开始更容易，但我有一些重要的注意事项：

1. You don't need division at all, you can instead multiply, so that you can get the same average over a slice of length 6 and avoid float operations altogether

2. You don't need division (or in my case multiplication) in the loop, once in the end it is enough.

3. If you had to actually do it, you should always compare two floating point numbers like so: EPSILON = 0.0000001 (depending on the precision you look for this can be a different number) and if Math.abs(averageTwo - averageThree) < EPSILON it means they are equal. And you don't need double precision, float is enough.

1. 您根本不需要除法，您可以改为乘法，这样您就可以在长度为 6 的切片上获得相同的平均值并完全避免浮点运算

2. 您不需要循环中的除法（或在我的情况下乘法），一旦结束就足够了。

3. 如果你必须真的这样做，你应该总是像这样比较两个浮点数：EPSILON = 0.0000001（取决于你寻找的精度，这可以是一个不同的数字）如果 Math.abs(averageTwo - averageThree) < EPSILON it意味着他们是平等的。而且你不需要双精度，浮点数就足够了。

Here is my solution in Java, it got 100% on Codility:

这是我在 Java 中的解决方案，它在 Codility 上获得了 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;
}

回答by FedMar

This is my solution written in C (scored 100%)

这是我用 C 编写的解决方案（得分 100%）

#include <string.h>

int solution(int A[], int N) {
    // write your code in C99

    int *p, i;
    float minAvg, tmpAvg;
    int index=0;

    p=malloc(sizeof(int)*(N+1));
    memset(p, 0, sizeof(int)*(N+1));

    if(N == 2) {
        return 0;
    }

    *p=0;

    //Building prefixes vector
    for(i=0;i<N;i++) {
        *(p+i+1)=*(p+i)+A[i];
    }

    minAvg=*(p+N)/(float)(N);

    for(i=0; i<N-1; i++) {
        tmpAvg=(*(p+i+2)-*(p+i))/(float)(2);
        if (tmpAvg < minAvg) {
            minAvg=tmpAvg;
            index=i;
        }
    }

    for(i=0; i<N-2; i++) {
        tmpAvg=(*(p+i+3)-*(p+i))/(float)(3);
        if (tmpAvg < minAvg) {
            minAvg=tmpAvg;
            index=i;
        }
    }

    free(p);
    return index;
}

回答by victor1ee

Here is a Go implementation:

这是一个 Go 实现：

func Solution(A []int) int {
    if len(A) < 2 {
        return -1
    }

    result := 0
    minAvg := float64(A[0]+A[1]) / 2
    var curAvg float64
    for index := 0; index < len(A)-2; index++ {
        curAvg = float64(A[index]+A[index+1]) / 2
        if curAvg < minAvg {
            minAvg = curAvg
            result = index
        }

        curAvg = float64(A[index]+A[index+1]+A[index+2]) / 3
        if curAvg < minAvg {
            minAvg = curAvg
            result = index
        }
    }

    curAvg = float64(A[len(A)-2]+A[len(A)-1]) / 2
    if curAvg < minAvg {
        minAvg = curAvg
        result = len(A) - 2
    }

    return result
}

回答by Ira

 public int solution(int[] A)
        {
//C# solution thats getting 100%. Once you find min avg with always within 2   //or 3 elements of moving index its much simpler sol
            int minIndex = 0;
            double minAvgVal = Double.MaxValue;

            for (int i = 0; i < A.Length-2; i++)
            {
                double twoDigitMin = (A[i] + A[i + 1])/2.0;
                if (minAvgVal > twoDigitMin)
                {
                    minAvgVal = twoDigitMin;
                    minIndex = i;
                }

                double threDigitMin = (A[i] + A[i + 1] + A[i+2]) / 3.0;
                if (minAvgVal > threDigitMin)
                {
                    minAvgVal = threDigitMin;
                    minIndex = i;
                }
            }

            double last2Avg = (A[A.Length - 2] + A[A.Length - 1])/2.0;
            if (minAvgVal > last2Avg)
            {
                minIndex = A.Length - 2;
            }

            return minIndex;
        }

回答by moxi

Here's another Java solution 100/100 using the prefix sums:

这是另一个使用前缀总和的 Java 解决方案 100/100：

public int solution(int[] A) {
        int len = A.length, result = len - 1, sum = 0;
        int[] prefixSums = new int[len + 1];

        for (int i = 1; i <= len; ++i) {
            prefixSums[i] = prefixSums[i-1] + A[i-1];
        }

        double min = Double.MAX_VALUE, average = 0d;

        for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P, ++Q ) {
            sum = prefixSums[Q + 1] - prefixSums[P];
            average = (sum)/(double) 2;

            if (average < min) {
                min = average;
                result = P;
            }

            if ( Q + 2 < prefixSums.length ) {
                sum = prefixSums[Q + 2] - prefixSums[P];
                average = (sum)/(double) 3;

                if (average < min) {
                    min = average;
                    result = P;
                }
            }

        }

        return result;
    }

Here's the codility link: https://codility.com/demo/results/demo4S4VJX-WMJ/

这是 codility 链接：https://codility.com/demo/results/demo4S4VJX-WMJ/