javascript - Codility - 最小平均切片

Question

我正在尝试找到 a codility question on minimum slice of a subarray 的解决方案，并且我使用 Kadane 算法的修改版本设计了一个解决方案。我目前得到了 90/100 并且设法通过了 O(n) 中的几乎所有测试。但是，我似乎无法通过“medium_range，增加，减少(legth = ~100)和小功能，得到 5 expected 3”，我不知道为什么。这可能是 solution 的重复，但我使用了一种稍微不同的解决方法。

我的逻辑是这样的:

a) 如果我们有一个数组 MinA，其中 MinA[k] 表示从 k 开始的最小长度为 2 的子数组的最小平均切片

b) 然后如果我们遍历 MinA 并找到数组的最小值，那么这将是整个数组的最小平均切片(然后返回索引位置)

c) 要创建这个 MinA，我们从数组的倒数第二个元素开始，MinA[A.length -2] 是 A 的最后两个元素的平均值

d) 我们将计数器向左移动一个位置； MinA[counter] 必须是 A[counter] 和 A[counter + 1] 的平均值，或者是元素 counter 和 MinA[counter + 1] 中元素的平均值

e) 如果 d 不为真，则这意味着 MinA[counter + 1] 不是从 counter + 1 到从 counter + 2 到 N 的某个元素的最小平均切片

我想知道我是否遗漏了什么？

/*
 * Using modified version of Kadane's algorithm
 * The key logic is that for an array A of length N, 
 * if M[k + 1] is the minimum slice of a subarray from k + 1 to any element
 * between k+2 to n, then M[k] is either the average of A[k] and A[k + 1], or
 * the average of the elements k and the elements in M[k + 1]
 */
function solution(A) {
    // you can use console.log for debugging purposes, i.e.
    // console.log('this is debug message');
    // write your code in JavaScript (ECMA-262, 5th edition)
    var minSliceArray = [],
        counter = A.length - 2,
        currMinSliceLength = 0,
        min = Number.POSITIVE_INFINITY,
        minIndex = -1;

    minSliceArray[counter] = (A[counter] + A[counter + 1]) / 2;
    currMinSliceLength = 2;
    counter--;

    while (counter >= 0) {
        var a = (A[counter] + A[counter + 1]) / 2,
            b = (A[counter] + minSliceArray[counter + 1] * currMinSliceLength) / (currMinSliceLength + 1) ;
        if (a < b) {
            minSliceArray[counter] = a;
            currMinSliceLength = 2;
        } else {
            minSliceArray[counter] = b;
            currMinSliceLength++;
        }
        counter--;
    }

    //loops through the minSliceArray and find the minimum slice
    for (var i = 0; i < minSliceArray.length; i++) {
        if (minSliceArray[i] < min) {
            min = minSliceArray[i];
            minIndex = i;
        }
    }
    return minIndex;
}

Answer 1

要解决您的问题，您可以替换代码

if (a < b) {

与

if (a <= b) {

例如A = [-3, 3, -3, 3, -3]，首先我们考虑的是A[3:5]，平均值为0。然后，我们来到位置2，A [2:5]/3 = -1，A[2:4]/2 = 0。所以我们选择前者。对于位置1，A[1:3]/2 == A[1:5]/4 == 0。在OLD答案中，我们应该继续选择A[1:5]。最后对于位置 0，我们有 A[0:2]/2 = 0，并且 A[0:5]/5 = -0.6 我们选择后者。毕竟，总体最小平均值位于位置 3，因为 A[3:5]/3=-1。 但是实际上是 A[0:3]/3 == -1 == A[3:5]/3。

因为这样的陷阱，我在博客中没有使用Kadane算法的修改版本。但它应该运作良好。