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

Question

• 我们正在尝试找出蛋糕中哪一 block 的平均值最高。

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

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

• 得出最高平均值的切片就是我们的答案

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