最小平均两片可挠性

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/

原文由 Jose P. 发布，翻译遵循 CC BY-SA 4.0 许可协议

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;
    }
}

原文由 cotupha 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

基于 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;
}

我对 ²⁄₃ 元素子切片解决方案不满意（来吧！谁会在采访期间想到这个？），也不满意解释（或没有解释），所以我继续寻找其他方法。然后我发现了 Kadane 的最大子数组问题 (MSP) 算法，这使我找到了不同的解决方案。

基本问题是（类似于 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 中的地方，但它可以很容易地被一个变量替换，该变量具有前一个切片的大小和另一个乘法。

原文由 Mr. Duhart 发布，翻译遵循 CC BY-SA 4.0 许可协议