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;
- Alle Elemente im Array summieren O(n)
- Erhalten Sie die Hälfte der Summe O(1)
- 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)
- Tun Sie das Gleiche für das Recht, um eine Summe rechts. O(n) .
- 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?