最低平均两片Codility

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).
例如,数组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/

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

希望能帮助到你!

但我刚看到它被主持人删除了.他们说这个链接已经死了,但我只是尝试过它并且工作正常.我再次发布它,希望可以验证链接是否良好.

现在我也可以根据我之前提供的codesays链接提供我的实现:https://codility.com/demo/results/demoERJ4NR-ETT/

干杯!

Answer 2

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

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

2. 你不需要在循环中进行除法(或者在我的情况下乘法),最后一次就足够了.

3. 如果您必须实际执行此操作,则应始终比较两个浮点数,如下所示:EPSILON = 0.0000001(取决于您查找的精度可能是不同的数字),如果Math.abs(averageTwo - averageThree)<EPSILON it意味着他们是平等的.而且你不需要双精度,浮动就足够了.

这是我在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;
}

Answer 3

   static public int solution(int[] A) {
    // write your code in Java SE 8

    float avg = 0f;
    int min_index = 0;
    int P = 0;
    //formula

    float sums[] = new float[A.length ];

    //suffix sums
    int prefix = 0;
    for (int i = 0; i < A.length; i += 1) {
        prefix += A[i];
        sums[i] += prefix;
    }
    float min_avg = Float.MAX_VALUE;
    for (int i = 1; i < A.length; i++) {
        avg = (sums[i] - sums[P] + A[P]) / (i - P + 1);
        if (avg < min_avg) {
            min_avg = avg;
            min_index = P;
        }

这个想法相当简单但并不那么简单，那A[P] + A[P + 1] + ... + A[Q]) / (Q ? P + 1)就是那里的公式，先计算前缀和。

公式：min_avg = (prefix[i] - prefix[P] + A[P]) / (i - P + 1)'

        if (A[i] < min_avg) {
            P = i;
        }
    }


    return min_index;


}

Answer 4

基于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）的Kadane算法，然后想到了另一种解决方案。

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

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

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

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

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

但是，在情况2中，我们发现增加前一个切片实际上会增加平均值。因此，我们再次从头开始，将切片（lft_idx）的开始“重置” 为上一个元素（i - 1）。现在，从这一点开始，我们将有一个新的最佳大小2的切片。

最后，我们需要全局最小平均值，因此我们需要跟踪到目前为止的最小值以及从何处开始（该问题仅要求这样做，但我们也可以保存正确的索引）。

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

Answer 5

这是一个数学问题...要解决该问题，您必须了解切片平均值之间存在的关系。

从问题描述中我们知道切片的最小长度为2。此问题的窍门是最小平均切片也不能大于3。因此，我们只需要计算长度为2和3的切片的平均值。

要了解为什么最小平均限度不能大于3，请考虑大于3的情况。

ex. [-10, 3, 4, -20]

avg(0,3) = -23 / 4 = -5.75 // entire array is -5.75 average
avg(0,1) = -7 / 2 = -3.5 // subslice (0,1)
avg(2,3) = -16 / 2 = -8 // subslice (2,3)

请注意，(avg(0,1) + avg(2,3)) / 2 = avg(0,3) 因此，如果avg(0,1) != avg(2,3)其中一个必须小于另一个。

无论我们采用哪种方式拆分此数组，如果条带都不完全相同，则其中之一的平均值必须低于整个条带。试一试，您会发现它是真的。那里有数学证明。

Answer 6

100％得分。Javascript。

var min_pos = 0;
var min = Number.MAX_VALUE;

function solution(A) {
  for (var a = 0; a < A.length - 2; a++) {
    process((A[a] + A[a + 1]) / 2.0, a);
    process((A[a] + A[a + 1] + A[a + 2]) / 3.0, a);
  }

  process((A[A.length - 2] + A[A.length - 1]) / 2.0, A.length - 2);
  return min_pos;
}

function process(val, a) {
  if (val < min) {
    min_pos = a;
    min = val;
  }
}