冷凝-最小平均切片

Question

我正试图找到一个子阵列最小切片的余数问题的解决方案，并且我已经设计了一个使用Kadane算法的修改版本的解决方案。我目前已经拿到了90/100，并且设法通过了O(n)的几乎所有考试。但是我好像过不了“medium_range，increasing，decreasing(legth = ~ 100)and small functional，got 5 expected 3”，我也不知道为什么。这可能是重复的解法，但是我用了一种稍微不同的解法。

我的逻辑如下：

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

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

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

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

e)如果d不为真，那么这意味着MinA[计数器1]不是从计数器1到从计数器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

怎么样

Javascript

function solution(A) {
    var minpos = 0,
        minavg = (A[0] + A[1]) / 2,
        N = A.length,
        N1 = N - 1,
        N2 = N - 2,
        sumTwo,
        t,
        i;

    for (i = 0; i < N2; i += 1) {
        sumTwo = A[i] + A[i + 1];
        t = sumTwo / 2;
        if (minavg > t) {
            minavg = t;
            minpos = i;
        }

        t = (sumTwo + A[i + 2]) / 3;
        if (minavg > t) {
            minavg = t;
            minpos = i;
        }

    }

    t = (A[N2] + A[N1]) / 2;
    if (minavg > t) {
        minavg = t;
        minpos = N2;
    }

    return minpos;
}

var A = [4, 2, 2, 5, 1, 5, 8];

console.log(solution(A));

在jsFiddle上

Answer 2

在第一次尝试时，我有一个O(2^NN)算法，这很简单，但只有40%的正确率和0%的性能:

function solution(A) {
    var m = null, c, n
    for ( var i = 0; i < A.length; ++i ) {
        for ( var j = i + 1; j <= A.length; ++j ) {
            c = A.slice(i, j + 1).reduce(function (a,b) { return a+b }) / (j - i + 1)
            if ( m === null || c < m ) {
                m = c
                n = i
            }
            else if ( c == m && i < n ) {
                n = i
            }
        }
    }
    return n
}

睡在上面，第二次尝试时想到了这个，得到了一个O（N）算法，获得了100%的正确性和100%的性能：

function solution(A) {
    if ( A.length < 2 )  return -1
    var result = A.reduce(function (a, b, bIndex) {
        var f = typeof a === 'number'
        var x, y, z
        z = {
            index: bIndex,
            value: b,
            couple: {
                start: bIndex - 1,
                sum:   x = (f ? a : a.value) + b,
                count: 2,
                avg:   x / 2
            },
            streak: {
                start: a.bestStreak ? a.bestStreak.start : 0,
                sum:   x = (f ? a : a.bestStreak.sum) + b,
                count: y = (f ? 1 : a.bestStreak.count) + 1,
                avg:   x / y
            }
        }

        z.bestStreak = z.couple.avg < z.streak.avg
            ? z.couple
            : z.streak

        z.best = !a.best || z.bestStreak.avg < a.best.avg
            ? z.bestStreak
            : a.best

        // console.log(JSON.stringify({z}, null, '  '))

        return z
    })
    return result.best.start
}

解决后，我环顾四周，看看别人是怎么做的。我认为我上面的解决方案是最容易理解和调试的。

它的工作原理是知道，如果条纹本身不包含较低的条纹，则没有条纹的平均值可以降低。

这可能看起来很奇怪，就像你可能会想的那样——如果我有一个平均连胜，然后是一个超低的数字，会发生什么？嗯，连胜中的最高数字永远不会是最后一个数字，因为这会增加连胜的平均值，打破它。所以最后一个数字要么是对连胜有利的数字，在这种情况下，下一个数字也可能是有益的，可能会形成一对更好的连胜，要么最后一个或当前的数字是连胜断路器，可以丢弃。

Answer 3

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

if (a < b) {

与

if (a <= b) {

例如A=[-3、3、-3、3和-3]，首先，我们考虑A[3:5]，平均值为0。然后，我们得到位置2，A[2:5]/3=-1，A[2:3]/2=0。因此，我们选择前者。对于位置1，A[1:3]/2==A[1:5]/4==0。在旧答案中，我们应该继续选择A[1:4]。最后，对于位置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。

由于这些陷阱，我没有在博客中使用卡丹算法的修改版本。但它应该很有效。