在数组中查找平衡点

Question

这个问题来自一个很棒的YouTube频道，给出了可以在采访中提出的问题。

它基本上与寻找数组中的平衡点有关。这里有一个例子来最好地解释它；{1,2,9,4,-1}.因为sum(1 ^ 2)= sum(4(-1))使9成为平衡点。在没有检查答案的情况下，我决定先实现这个算法，想问问是否有更有效的方法；

< li >对数组O(n)中的所有元素求和 得到总数的一半O(1) < li >从左侧开始扫描数组，当< b>sumleft大于一般总和的一半时停止。O(n) < li >对右侧进行同样的操作，以获得< b>sum right。O(n)。 < li >如果sumleft等于sumright，则返回arr[size/2]，否则返回-1

我之所以问这个问题，是因为这个解决方案毫不费力地出现在我的脑海中，提供了O（n）的运行时间。如果这种解决方案是真的，是否可以开发，或者如果不是真的，是否有任何替代方法？

Answer 1

我实际上有两个起点，一个在最左边的点（leftLoc），一个在右边的点（rightLoc）。保持左和右数字相加。

leftLoc  = 0;
rightLoc = (n - 1);
sumRight = array[rightLoc];
sumLeft  = array[leftLoc];

while(leftLoc < rightLoc){
    if(sumRight > sumLeft){
        leftLoc++;
        sumLeft += array[leftLoc];
    }else{
        rightLoc--;
        sumRight += array[rightLoc];
    } 
}

if( (sumRight + array[rightLoc - 1]) == sumLeft ){
    return rightLoc--;
}else if( (sumLeft + array[leftLoc + 1]) == sumRight){
    return leftLoc++;
}else{
    // return floating point number location in the middle of the 2 locations
}

同时跟踪已移动 O（n） 的总位置数

您可能会发现您的平衡点是最后点中间的浮点数（一旦它们位于彼此相邻的整数位置）。

这甚至适用于负数的例子。也许我遗漏了一些细节，但是这个主题的一些变化应该会产生O(n)运行时算法。

Answer 2

匿名用户

基本上先把所有的数字加起来。这将是一个O（n）操作。然后从数组的开头开始，一次从数组中减去一个元素，直到＜code＞上限＝＝＜code＞下限。因此，总阶数为O（n）。

int BalancePoint(int a[], int begin, int end) // find index of an array (balance point) such that sum of all elements before the index = sum of all elements after it; else return -1
{
    if(!a) return -1;
    else if(begin == end) return begin;

        long long upper = 0;
        long long lower = 0;

    for(int i = begin; i <= end; ++i)
    {
        upper += *(a+i);
    }

    for(int j = begin; j <= end; ++j)
    {
        upper -= *(a+j);
        if(upper == lower) return j;
        lower += *(a+j);
    }
    return -1;
}

使用STL

int BalancePointSTL( const vector<int> &A ) // find index of an array (balance point) such that sum of all elements before the index = sum of all elements after it; else return -1
{
    if(A.empty()) return -1;

        long long upper = 0;
        long long lower = 0;

    for(unsigned int i = 0; i <= A.size(); ++i)
    {
        upper += A[i];
    }

    for(unsigned int j = 0; j < A.size(); ++j)
    {
        upper -= A[j];
        if(upper == lower) return j;
        lower += A[j];
    }
    return -1;
    }

以下将具有更好的最坏情况性能，但会有更多的if-fe比较

int BalancePoint2(int a[], int begin, int end) // Better worst case senario by factor of 2
{
    if(!a) return -1;
    else if(begin == end) return begin;

        long long upper = 0;
        long long lower = 0;

        int mid = (end-begin)/2;

        for(int i = begin; i < mid; ++i)
        {
            lower += *(a+i);
        }
        for(int i = mid+1; i <= end; ++i)
        {
            upper += *(a+i);
        } 

        if(upper == lower) return mid;
        else if(lower < upper)
        {
            lower += *(a+mid);
            for(int i= mid + 1 ; i <= end ; ++i)
            {
                upper -= *(a + i);
                if(upper == lower) return i;
                lower += *(a + i);
            }
        }
        else {
            upper += *(a + mid);
            for(int i = mid - 1; i >=begin; --i)
            {
                lower -= *(a + i);
                if(upper == lower) return i;
                upper += *(a + i);
            }
        }
        return -1;
}

Answer 3

你的算法不好（反例：1-1011-1111），好的解决方案是计算数组的部分和（这样你就可以为数组的每个单元格计算O（1）中的sumleet和Sumlright），然后（或者如果你已经知道全局和），在数组中搜索一个单元格，使得SUmleet=sumlright>/code>，这是O（n）。

数组A的部分和是

[A[0], A[0]+A[1], A[0]+A[1]+A[2], …, A[0]+A[1]+A[2]+…+A[n-1]]

示例：

A=[5,2,3,1,4,6]
partial sum = [5,7,10,11,15,21]

使用这个数组，您可以计算sum right[i]=partial_sum[i-1]和sum right[i]=partial_sum[n-1]-partial_sum[i]

改进：

如果存储所有的partial_sum数组，则首先计算全局和，然后只计算当前索引的部分和，这样可以只使用O(1)个额外空间，而不是O(n)个额外空间。