java - 如果我们有一块蛋糕，那么在数组中找到最高平均值的最有效算法是什么？

Question

• 我们正试图找出蛋糕中的哪一块是最高的平均值。

• 蛋糕有数字 [ 1, 3, 4, 2, 2 ]

• 片 [3, 4] 的平均结果为 3.5

• 导致最高平均值的切片是我们的答案

标签： java

Answer 1

是的，你当然可以在 O(N) 时间内做到这一点。我想说我在很短的时间内就知道了这一点，以便进行工作面试，但我认为那是谎言。

诀窍是：您只需要考虑从任一端开始的切片。

证明：如果剩下的余数由两部分组成，则余数的平均值将介于两部分的平均值之间。如果你扔掉平均值较低的那块，那么整体平均值会上升。如果两个部分的平均值相同，那么您可以丢弃任何一个，并且整体平均值不会改变。

static int[] getBestSlice(int[] cake)
{
    if (cake == null || cake.length < 1)
    {
        throw new IllegalArgumentException("THE CAKE IS A LIE!");
    }
    long leftSum = cake[0];
    long rightSum = cake[cake.length-1];
    long bestLeftSum = leftSum;
    long bestRightSum = rightSum;
    int bestLeftLen=1;
    int bestRightLen=1;
    for (int len=2; len<=cake.length; ++len)
    {
        leftSum += cake[len-1];
        rightSum += cake[cake.length-len];
        // a/b > c/d <=> ad > cb
        if (leftSum*bestLeftLen > bestLeftSum*len)
        {
            bestLeftSum = leftSum;
            bestLeftLen = len;
        }
        if (rightSum*bestRightLen > bestRightSum*len)
        {
            bestRightSum = rightSum;
            bestRightLen = len;
        }
    }
    if (bestLeftSum*bestRightLen > bestRightSum*bestLeftLen)
    {
        //best remainder is on the left -- slice off the right
        return new int[]{bestLeftLen, cake.length-bestLeftLen};
    }
    else
    {
        //best remainder is on the right -- slice off the left
        return new int[]{0,cake.length-bestRightLen};
    }
}