Find Pivot Index
Du erhältst ein Array von Ganzzahlen nums. Ein Pivot-Index ist ein Index, bei dem die Summe der Werte links davon der Summe der Werte rechts davon entspricht. Der Wert am Pivot selbst gehört zu keiner der beiden Seiten, und eine Seite ohne Werte hat die Summe 0.
Gib den am weitesten links liegenden Pivot-Index zurück oder -1, wenn kein Index ein Pivot ist.
Funktion
- numsinteger-array
- das Array aus Ganzzahlen, das ausgeglichen werden soll
- Gibt zurückinteger
- der Index des am weitesten links liegenden Pivots oder -1, wenn es keinen gibt
Einschränkungen
1 ≤ nums.length ≤ 104-1000 ≤ nums[i] ≤ 1000
Beispiele
- Eingabe
- nums = [3, 1, 5, 2, 2]
- Ausgabe
- 2
- Erklärung
- Bei Index 2 ist die linke Seite 3 + 1 = 4 und die rechte Seite 2 + 2 = 4. Index 0 und Index 1 sind nicht im Gleichgewicht (links 0 gegenüber 10, links 3 gegenüber 9), daher ist 2 der am weitesten links liegende Drehpunkt.
- Eingabe
- nums = [1, 2, 3]
- Ausgabe
- -1
- Erklärung
- Die drei Kandidaten ergeben 0 gegen 5, 1 gegen 3 und 3 gegen 0. Kein Index gleicht sich aus, daher lautet die Antwort
-1.
- Eingabe
- nums = [4, -4, 9]
- Ausgabe
- 2
- Erklärung
- Bei Index 2 ist die linke Seite 4 + (-4) = 0, und die rechte Seite ist leer, also ergibt ihre Summe ebenfalls 0. Der letzte Index kann der Drehpunkt sein.
+17 versteckte Tests beim Einreichen
Weiterführende Frage
Kannst du das am weitesten links liegende Pivot finden, indem du jeden Wert nur einmal liest, ohne zuerst die Summe zu berechnen? Wie viel Speicher benötigt das?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Um einen Index zu überprüfen, benötigt man zwei Summen: die Werte davor und die Werte danach. Sie für jeden Index erneut zu addieren, wiederholt fast die gesamte Arbeit. Wie hängen die beiden Summen für den Index
imit denen für den Indexi+1zusammen?Ein Schritt nach rechts addiert
nums[i]zur linken Summe. Und sobald du die Gesamtsumme des Arrays kennst, ergibt sich die rechte Summe aus der linken: Sie ist die Gesamtsumme minus die linke Summe minusnums[i].Addiere zuerst das gesamte Array. Gehe dann von links nach rechts und führe dabei eine laufende linke Summe. Vergleiche an jedem Index die linke Summe mit der Gesamtsumme minus der linken Summe minus dem aktuellen Wert; gib beim ersten Treffer den Index zurück und addiere den aktuellen Wert erst nach dem Vergleich zur linken Summe. Wenn die Schleife endet, gib -1 zurück.
Lösung
Einen Index zu überprüfen, erfordert zwei Summen, aber wenn man sie an jedem Index neu berechnet, wächst der Aufwand mit dem Quadrat der Länge. Die Lösung besteht darin, die Neuberechnung zu vermeiden: Die linke Summe wächst bei jedem Schritt um einen Wert, und die rechte Summe ist einfach der Rest der Gesamtsumme. Ein Durchlauf für die Gesamtsumme und ein zweiter Durchlauf mit einer laufenden linken Summe finden den am weitesten links liegenden Pivot, wobei zwei Zahlen im Speicher gehalten werden.
An jedem Index beide Seiten addieren
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Folge der Definition. Addiere für jeden Index i die Werte davor, addiere die Werte danach und vergleiche die Summen. Der erste Index, bei dem die beiden Summen übereinstimmen, ist die Antwort, weil du die Indizes von links nach rechts durchgehst.
Die Randfälle erledigen sich von selbst. Bei Index 0 wird die linke Schleife kein einziges Mal ausgeführt, daher ist die linke Summe 0; beim letzten Index wird die rechte Schleife kein einziges Mal ausgeführt. Deshalb gibt [4, -4, 9] den Wert 2 zurück.
Das Problem ist der Aufwand. Für jeden Index werden die anderen n-1 Werte addiert, daher beträgt der Gesamtaufwand ungefähr n² Additionen. Bei 10.000 Werten sind das fast 100 Millionen Additionen, von denen die meisten Summen wiederholen, die du bereits einen Index zuvor berechnet hast.
Algorithmus
- Durchlaufe
ifür jeden Index vonnums. - Addiere
nums[0]bisnums[i-1]zur linken Summe. - Addiere
nums[i+1]bis zum letzten Wert zur rechten Summe. - Wenn die beiden Summen gleich sind, gib
izurück. - Wenn kein Index übereinstimmt, gib -1 zurück.
def pivotIndex(nums):
n = len(nums)
for i in range(n):
left = 0
for j in range(i):
left += nums[j]
right = 0
for j in range(i + 1, n):
right += nums[j]
if left == right:
return i
return -1Präfixsummenarray
Idee
Bei der Brute-Force-Methode werden die Summen der Teilarrays immer wieder berechnet. Ein Präfixsummenarray erledigt diese Arbeit einmal. Sei prefix[k] die Summe der ersten k Werte, wobei prefix[0] = 0. Für [3, 1, 5, 2, 2] ergibt sich [0, 3, 4, 9, 11, 13].
Jetzt lässt sich jede Teilsumme als Differenz zweier Einträge berechnen. Die linke Seite des Index i umfasst die ersten i Werte, also prefix[i]. Die rechte Seite umfasst alles nach nums[i], also prefix[n] - prefix[i+1]. Am Index 2 ergibt das links 4 und rechts 13 - 9 = 4 – ein Pivot.
Das Erstellen des Arrays erfordert einen Durchlauf, und jede Prüfung benötigt konstante Zeit. Die gesamte Suche läuft also in O(n). Dafür werden n+1 zusätzliche Zahlen im Speicher benötigt.
Algorithmus
- Erstelle
prefixder Längen+1mitprefix[0] = 0. - Fülle es:
prefix[k+1] = prefix[k] + nums[k]. - Lies für jeden Index
idie linke Summe alsprefix[i]und die rechte Summe alsprefix[n] - prefix[i+1]. - Gib den ersten
izurück, bei dem sie gleich sind, oder nach der Schleife -1.
def pivotIndex(nums):
n = len(nums)
# prefix[k] is the sum of the first k values.
prefix = [0] * (n + 1)
for k in range(n):
prefix[k + 1] = prefix[k] + nums[k]
for i in range(n):
left = prefix[i]
right = prefix[n] - prefix[i + 1]
if left == right:
return i
return -1Gesamtsumme und laufende Summe von links
Idee
Sieh dir an, welche Präfixeinträge der vorherige Ansatz liest. Am Index i benötigt er prefix[i], prefix[i+1] und prefix[n]. Letzteres ist die Gesamtsumme, die sich nie ändert; die anderen beiden entsprechen der laufenden Summe, die du erhältst, wenn du das Array einmal durchläufst. Du kannst also statt des ganzen Arrays die Gesamtsumme und eine laufende linke Summe speichern.
Jeder Wert liegt entweder links, am Pivot oder rechts. Die rechte Summe ist also die Gesamtsumme minus die linke Summe minus nums[i]. Für [3, 1, 5, 2, 2] beträgt die Gesamtsumme 13. Am Index 0 ist die linke Summe 0 und die rechte Summe 13 - 0 - 3 = 10. Am Index 1 steht sie 3 zu 9. Am Index 2 steht sie 4 zu 13 - 4 - 5 = 4, also gibst du 2 zurück.
Die Reihenfolge innerhalb der Schleife ist wichtig. Vergleiche zuerst und addiere dann nums[i] zur linken Summe, damit diese nie den Wert am gerade geprüften Index enthält. Wenn du beim ersten Treffer zurückkehrst, erhältst du den am weitesten links liegenden Pivot.
Du durchläufst das Array zweimal: einmal für die Gesamtsumme und einmal für die Suche. Daher beträgt die Laufzeit O(n). Es werden nur zwei Zahlen gespeichert, daher beträgt der zusätzliche Speicherbedarf O(1).
Algorithmus
- Addiere alle Werte zu
total. - Setze
leftauf 0. - Wenn für jeden Index
igilt, dassleftgleichtotal - left - nums[i]ist, gibizurück. - Addiere andernfalls
nums[i]zuleftund fahre fort. - Wenn die Schleife endet, gib -1 zurück.
def pivotIndex(nums):
total = sum(nums)
left = 0
for i, value in enumerate(nums):
# Everything that is not on the left and not nums[i] is on the right.
if left == total - left - value:
return i
left += value
return -1
Stolperfallen und Grenzfälle
Die meisten falschen Antworten setzen den Wert des Pivots auf eine Seite oder überspringen einen Randindex.
nums[i]vor dem Vergleich zur linken Summe hinzufügen. Dann enthält die linke Seite den Pivotwert, und für[3, 1, 5, 2, 2]wird der Index 2 nicht mehr gefunden.- Die rechte Seite als
total - leftberechnen. Dadurch wirdnums[i]auf der rechten Seite mitgezählt; ziehe es ebenfalls ab. - Index 0 oder den letzten Index überspringen. Beide können der Pivot sein, da die Summe einer leeren Seite 0 beträgt.
[1, -1, 1]gibt 0 zurück und[4, -4, 9]gibt 2 zurück. - Den letzten statt des ersten Treffers zurückgeben. In
[0, 0, 0]sind alle Indizes ausgeglichen, und die Antwort ist 0. - Zwei Zeiger verwenden, die sich von beiden Enden nach innen bewegen und die kleinere Seite vergrößern. Das funktioniert nur, wenn alle Werte nicht-negativ sind; hier reichen die Werte bis -1000, sodass eine Seite beim Wachsen schrumpfen kann.
- Vergessen, dass Lua- und R-Arrays bei 1 beginnen. Gib
i-1zurück, damit die Antwort ein 0-basierter Index ist.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität von Find Pivot Index?
Die Lösung mit Gesamtsumme und laufender Summe benötigt O(n) Zeit: einen Durchlauf, um das Array zu summieren, und einen weiteren, um es zu durchlaufen. Sie benötigt O(1) zusätzlichen Speicherplatz. Beide Seiten an jedem Index neu zu berechnen, benötigt stattdessen O(n²) Zeit.
Warum ist die rechte Summe gleich der Gesamtsumme minus der linken Summe minus nums[i]?
Jeder Wert des Arrays befindet sich genau an einer von drei Stellen: links von i, bei i oder rechts von i. Ihre Summen ergeben zusammen die Gesamtsumme, daher ist die rechte Summe die Gesamtsumme abzüglich der beiden anderen Teile. So kannst du einen Index überprüfen, ohne jemals die rechte Seite aufzusummieren.
Kann Find Pivot Index mit zwei Zeigern gelöst werden?
Nicht zuverlässig. Ein Scan mit zwei Zeigern, der immer die kleinere Seite vergrößert, setzt voraus, dass das Hinzufügen eines Werts eine Seite größer macht. Das trifft nicht mehr zu, sobald Werte negativ sein können: Eine Seite kann schrumpfen, während du sie vergrößerst, sodass der Scan einen Zeiger über den tatsächlichen Pivot hinaus bewegen kann. Die Methode mit der laufenden Summe macht keine Annahmen über die Vorzeichen und prüft jeden Index.
Was ist der Pivotindex eines Arrays mit einem Element?
Es ist 0. Beide Seiten des einzigen Elements sind leer, und eine leere Seite ergibt in der Summe 0, also sind beide Seiten gleich. Die Lösung mit der laufenden Summe gibt bei ihrem ersten Vergleich 0 zurück: links ist 0 und die Gesamtsumme minus 0 minus der Wert ergibt ebenfalls 0.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def pivotIndex(nums):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums = [3, 1, 5, 2, 2]
Erwartet
2