c++ - 配列内のバランスポイントを見つける

Question

この質問は素晴らしいYouTubeチャンネルからのもので、インタビューで尋ねることができる問題を与えています。

これは基本的に、配列内のバランスポイントを見つけることに関連しています。これを最もよく説明する例を次に示します。{1,2,9,4、-1}。ここでは、sum（1 + 2）= sum（4 +（-1））であるため、9がバランスポイントになります。答えを確認せずに、より効率的なアプローチを実行できるかどうかを尋ねる前に、アルゴリズムを実装することにしました。

1. 配列O（n）のすべての要素を合計します
2. 合計の半分を取得するO（1）
3. 配列のスキャンを左から開始し、sumleftが一般的な合計の半分より大きくなったら停止します。の上）
4. 合計 の権利を取得するには、権利についても同じことを行います。O（n）。
5. sumleftがsumrightと等しい場合はarr[size/ 2]を返し、そうでない場合は-1を返します。

このソリューションが何の努力もせずに頭に浮かび、O（n）の実行時間を提供したので、私は尋ねています。このソリューションは、真の場合は開発できますか、それとも真でない場合は別の方法がありますか？

Answer 1

あなたのアルゴリズムは良くありません（反例：） 、良い解決策は、配列の部分和を計算することです（配列の各セルに対して O(1)で1 -1 1 0 1 -1 1計算できるように）そして（または同じでグローバル合計がすでにわかっている場合は時間）、配列でO（n）のセルを検索します。sumleftsumrightsumleft = sumright

配列の部分和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]

この配列を使用すると、計算sumleft[i]=partial_sum[i-1]してsumright[i]=partial_sum[n-1]-partial_sum[i]

改善：

最初にグローバル合計を計算し、次に現在のインデックスの部分合計のみを計算すると、すべての partial_sum 配列を格納する場合、O(n) の余分なスペースではなく、O(1) の余分なスペースのみを使用できます。

Answer 2

基本的に最初にすべての数値を合計します。これは O(n) 操作になります。次に、配列の先頭からupper==まで、一度に 1 つの要素を配列から減算しlowerます。したがって、合計順序は 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-else比較があります

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

実際には 2 つの開始点があり、1 つは一番左の点 (leftLoc) で、もう 1 つは右端の点 (rightLoc) です。sumLeft と sumRight の数値を保持します。

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 4

あなたはCenter of Massを探していると思います。ここに Go で書かれた解決策があります:

func centerOfGravity(a []int) float64 {
  tot := 0.0
  mass := 0.0
  for i := range a {
    tot += float64(i) * float64(a[i])
    mass += float64(a[i])
  }
  return tot / mass
}

これにより、0 から始まる配列を想定して、配列内の重心のインデックスが得られます。質量の中心は配列の範囲内のどこにでもある可能性があるため、整数以外の結果を返す可能性があります。