6 Stimmen

Suche nach dem Gleichgewichtspunkt in einem Array

Diese Frage stammt von einem großartigen youtube-Kanal, der Probleme aufzeigt, die in Vorstellungsgesprächen gestellt werden können.

Im Grunde geht es darum, den Gleichgewichtspunkt in einem Array zu finden. Hier ist ein Beispiel, das es am besten erklärt; {1,2,9,4,-1}. Da hier Summe(1+2)=Summe(4+(-1)) ist, ist die 9 der Gleichgewichtspunkt . Ohne die Antwort zu überprüfen, habe ich beschlossen, den Algorithmus zu implementieren, bevor ich fragen wollte, ob ein effizienterer Ansatz möglich ist;

  1. Alle Elemente im Array summieren O(n)
  2. Erhalten Sie die Hälfte der Summe O(1)
  3. Beginnen Sie mit dem Scannen des Arrays von links und stoppen Sie, wenn die sumleft größer ist als die Hälfte der allgemeinen Summe. O(n)
  4. Tun Sie das Gleiche für das Recht, um eine Summe rechts. O(n) .
  5. Si sumleft ist gleich sumright return arr[size/2] sonst Rückgabe -1

Ich frage, weil mir diese Lösung ohne jede Anstrengung in den Sinn gekommen ist und die O(n)-Laufzeit liefert. Ist diese Lösung, wenn wahr, könnte entwickelt werden, oder wenn nicht wahr keine alternativen Methoden?

6voto

Thomash Punkte 6323

Ihr Algorithmus ist nicht gut (Gegenbeispiel: 1 -1 1 0 1 -1 1 ), ist es eine gute Lösung, die Partialsumme Ihres Arrays zu berechnen (so dass Sie auch die sumleft y sumright in O(1) für jede Zelle des Arrays) und suchen Sie dann (oder in der gleichen Zeit, wenn Sie die globale Summe bereits kennen) in Ihrem Array eine Zelle, so dass sumleft = sumright was O(n) ist.

Die Partialsumme des Arrays A est

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

Beispiel:

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

Mit diesem Array können Sie folgende Berechnungen durchführen sumleft[i]=partial_sum[i-1] y sumright[i]=partial_sum[n-1]-partial_sum[i]

Verbesserung:

Durch die Berechnung der Gesamtsumme zuerst und dann nur der Teilsumme für den aktuellen Index benötigen Sie nur O(1) zusätzlichen Platz statt O(n) zusätzlichen Platz, wenn Sie das gesamte Array partial_sum speichern.

1voto

trumpetlicks Punkte 7003

Ich würde eigentlich 2 Startpunkte haben, einen am äußersten linken Punkt (leftLoc), und einen am äußersten rechten Punkt (rightLoc). Halten Sie eine sumLeft und sumRight Zahlen.

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
}

Dabei wird die Anzahl der insgesamt verschobenen Positionen verfolgt O(n)

Es kann sein, dass Ihr Ausgleichspunkt eine Fließkommazahl in der Mitte der Endpunkte ist (wenn sie an den ganzzahligen Stellen direkt nebeneinander liegen).

この sollte sogar mit dem Beispiel der negativen Zahlen arbeiten. Vielleicht übersehe ich einige Feinheiten, aber eine Variation dieses Themas sollte zu einem Algorithmus mit einer Laufzeit von O(n) führen.

1voto

Chinmay Nerurkar Punkte 495

Zählen Sie zunächst alle Zahlen zusammen. Dies ist eine O(n)-Operation. Dann subtrahieren Sie jeweils ein Element aus dem Array, beginnend mit dem Anfang des Arrays bis upper == lower . Die Gesamtordnung ist also 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 verwenden

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

Die folgenden Maßnahmen würden im ungünstigsten Fall eine bessere Leistung erbringen, aber es sind noch ein paar mehr if-else Vergleiche

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

0voto

Kenan Punkte 11628

Eine Lösung, die O(n) ist und nicht mehr Platz benötigt

def balance_array(arr):
    if len(arr) < 3:
        return False

    for i in range(1, len(arr)+1):
        lsum = sum(arr[:i])
        rsum = sum(arr[(i+1):])
        if lsum == rsum:
            return True
    return False

Prüfung

test_arrays = [[5, 3, 7, 0, 9], [5,2,3,1,4,6], [1,0,1], [1,6,5,1,2,3,1], [1,1], [], [1], [1,2,9,4,-1], [5, 4, 7, 0, 9], [1, -1, 1, 0, 1, -1, 1]]

for i in test_arrays:
    print(f'{i}\t{balance_array(i)}')

[5, 3, 7, 0, 9]         False
[5, 2, 3, 1, 4, 6]      True
[1, 0, 1]               True
[1, 6, 5, 1, 2, 3, 1]   True
[1, 1]                  False
[]                      False
[1]                     False
[1, 2, 9, 4, -1]        True
[5, 4, 7, 0, 9]         True
[1, -1, 1, 0, 1, -1, 1] True

-1voto

Running Wild Punkte 2933

Ich glaube, Sie suchen nach dem Zentrum der Masse Hier ist eine in Go geschriebene Lösung:

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
}

Damit erhalten Sie den Index des Massenschwerpunkts in der Matrix, wobei von einer 0-basierten Matrix ausgegangen wird. Es kann ein nicht ganzzahliges Ergebnis zurückgegeben werden, da der Schwerpunkt überall im Bereich des Arrays liegen kann.

CodeJaeger.com

CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.

Powered by:

X