java - 最小平均两片可塑性

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

基于 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 元素子切片解决方案不满意(来吧!谁会在面试期间想到这个？)，也不满意解释(或缺乏解释)，所以我继续寻找其他方法。然后我发现了Kadane's algorithm对于最大子阵列问题 (MSP)，这导致我找到了不同的解决方案。

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

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

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

1. A[lft_idx : i] 的平均值最小。
2. A[i - 1 : i] 的平均值最小(最短的切片有 2 个元素)。

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

然而，在情况 2 中，我们发现增加前一个切片实际上会增加平均值。因此，我们重新开始并将切片的开头 (lft_idx) “重置”为前一个元素 (i - 1)。现在我们有了一个新的 best 大小为 2 的切片，从这一点开始增长。

最后，我们想要 global 最小平均值，因此我们需要跟踪到目前为止的最小值以及它开始的位置(问题只要求这样做，但我们也可以保存正确的索引)。

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