Find Pivot Index
Otrzymujesz tablicę liczb całkowitych nums. Indeks równowagi to indeks, dla którego suma wartości po jego lewej stronie jest równa sumie wartości po jego prawej stronie. Wartość na samym indeksie równowagi nie należy do żadnej ze stron, a suma strony, na której nie ma żadnych wartości, wynosi 0.
Zwróć najbardziej lewy indeks równowagi lub -1, jeśli żaden indeks nie jest indeksem równowagi.
Funkcja
- numsinteger-array
- tablica liczb całkowitych do zrównoważenia
- Zwracainteger
- indeks skrajnie lewego elementu rozdzielającego lub -1, jeśli go nie ma
Ograniczenia
1 ≤ nums.length ≤ 104-1000 ≤ nums[i] ≤ 1000
Przykłady
- Wejście
- nums = [3, 1, 5, 2, 2]
- Wyjście
- 2
- Wyjaśnienie
- Pod indeksem 2 lewa strona to 3 + 1 = 4, a prawa strona to 2 + 2 = 4. Indeks 0 i indeks 1 nie są zrównoważone (lewa strona 0 w porównaniu z 10, lewa strona 3 w porównaniu z 9), więc 2 to najbardziej lewy punkt równowagi.
- Wejście
- nums = [1, 2, 3]
- Wyjście
- -1
- Wyjaśnienie
- Trzej kandydaci uzyskują odpowiednio 0 przeciwko 5, 1 przeciwko 3 i 3 przeciwko 0. Żaden indeks nie zapewnia równowagi, więc odpowiedzią jest
-1.
- Wejście
- nums = [4, -4, 9]
- Wyjście
- 2
- Wyjaśnienie
- Pod indeksem 2 lewa strona wynosi 4 + (-4) = 0, a prawa strona jest pusta, więc jej suma również wynosi 0. Ostatni indeks może być punktem podziału.
+17 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Czy potrafisz znaleźć skrajny lewy punkt podziału, odczytując każdą wartość tylko raz, bez wcześniejszego sumowania całości? Ile pamięci to kosztuje?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Sprawdzenie jednego indeksu wymaga obliczenia dwóch sum: wartości przed nim i wartości po nim. Ponowne dodawanie ich dla każdego indeksu powtarza prawie całą pracę. Jaki jest związek między dwiema sumami dla indeksu
ia sumami dla indeksui+1?Przesunięcie o jeden krok w prawo dodaje
nums[i]do sumy po lewej stronie. A gdy znasz sumę całej tablicy, suma po prawej stronie wynika z sumy po lewej: jest równa sumie całkowitej minus suma po lewej stronie minusnums[i].Najpierw zsumuj całą tablicę. Następnie przejdź od lewej do prawej, na bieżąco obliczając sumę po lewej stronie. Przy każdym indeksie porównaj sumę po lewej stronie z wartością całkowitą pomniejszoną o sumę po lewej stronie i bieżącą wartość; przy pierwszym dopasowaniu zwróć indeks, a dopiero po porównaniu dodaj bieżącą wartość do sumy po lewej stronie. Jeśli pętla się zakończy, zwróć -1.
Rozwiązanie
Sprawdzenie jednego indeksu wymaga obliczenia dwóch sum, ale ponowne ich obliczanie dla każdego indeksu sprawia, że ilość pracy rośnie wraz z kwadratem długości. Rozwiązaniem jest zaprzestanie ponownych obliczeń: lewa suma zwiększa się o jedną wartość w każdym kroku, a prawa suma to po prostu to, co pozostało z sumy całkowitej. Jedno przejście obliczające sumę całkowitą, a następnie drugie przejście z bieżącą lewą sumą pozwalają znaleźć najbardziej lewy punkt podziału, mając w pamięci dwie liczby.
Dodaj obie strony na każdym indeksie
Poprawne, ale nie kończy się na największych testach
Intuicja
Postępuj zgodnie z definicją. Dla każdego indeksu i zsumuj wartości przed nim, zsumuj wartości po nim i porównaj te sumy. Pierwszy indeks, dla którego sumy są równe, jest odpowiedzią, ponieważ sprawdzasz indeksy od lewej do prawej.
Skraje rozwiązują się same. Przy indeksie 0 lewa pętla wykonuje się zero razy, więc lewa suma wynosi 0; przy ostatnim indeksie prawa pętla wykonuje się zero razy. Dlatego [4, -4, 9] zwraca 2.
Problemem jest koszt. Dla każdego indeksu sumujesz pozostałe n-1 wartości, więc łączna praca to około n² dodawań. Przy 10,000 wartościach oznacza to prawie 100 million dodawań, a większość z nich powtarza sumy obliczone już o jeden indeks wcześniej.
Algorytm
- Wykonaj pętlę po każdym indeksie
itablicynums. - Zsumuj wartości od
nums[0]donums[i-1]jako sumę po lewej stronie. - Zsumuj wartości od
nums[i+1]do ostatniej wartości jako sumę po prawej stronie. - Jeśli obie sumy są równe, zwróć
i. - Jeśli żaden indeks nie pasuje, zwróć -1.
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 -1Tablica sum prefiksowych
Intuicja
Metoda brute force sumuje kolejne fragmenty tablicy. Tablica sum prefiksowych wykonuje tę pracę raz. Niech prefix[k] oznacza sumę pierwszych k wartości, przy czym prefix[0] = 0. Dla [3, 1, 5, 2, 2] będzie to [0, 3, 4, 9, 11, 13].
Teraz suma dowolnego fragmentu jest różnicą dwóch wartości. Lewa strona indeksu i obejmuje pierwsze i wartości, więc jest równa prefix[i]. Prawa strona obejmuje wszystko po nums[i], czyli prefix[n] - prefix[i+1]. Dla indeksu 2 daje to 4 po lewej stronie i 13 - 9 = 4 po prawej — jest to indeks równowagi.
Utworzenie tablicy wymaga jednego przejścia, a każde sprawdzenie zajmuje stały czas, więc całe wyszukiwanie ma złożoność O(n). Ceną jest n+1 dodatkowych liczb w pamięci.
Algorytm
- Utwórz
prefixo długościn+1zprefix[0] = 0. - Wypełnij go:
prefix[k+1] = prefix[k] + nums[k]. - Dla każdego indeksu
iodczytaj sumę po lewej stronie jakoprefix[i], a sumę po prawej stronie jakoprefix[n] - prefix[i+1]. - Zwróć pierwsze
i, dla którego są równe, albo -1 po pętli.
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 -1Suma całkowita i bieżąca suma po lewej stronie
Intuicja
Przyjrzyj się, z których elementów tablicy prefiksowej korzysta poprzednie podejście. Dla indeksu i potrzebuje prefix[i], prefix[i+1] i prefix[n]. Ostatni z nich to suma całkowita, która nigdy się nie zmienia, a dwa pozostałe odpowiadają sumie narastającej, którą uzyskałbyś, przechodząc przez tablicę jeden raz. Możesz więc przechowywać sumę całkowitą i jedną narastającą sumę po lewej stronie zamiast całej tablicy.
Każda wartość znajduje się po lewej stronie, w punkcie podziału albo po prawej stronie. Suma po prawej stronie to zatem suma całkowita minus suma po lewej stronie minus nums[i]. Dla [3, 1, 5, 2, 2] suma całkowita wynosi 13. Dla indeksu 0 suma po lewej stronie wynosi 0, a po prawej 13 - 0 - 3 = 10. Dla indeksu 1 wynosi odpowiednio 3 i 9. Dla indeksu 2 suma po lewej stronie wynosi 4, a po prawej 13 - 4 - 5 = 4, więc zwracasz 2.
Kolejność operacji w pętli ma znaczenie. Najpierw porównaj sumy, a potem dodaj nums[i] do sumy po lewej stronie, dzięki czemu ta suma nigdy nie obejmuje wartości o sprawdzanym indeksie. Zwrócenie wyniku przy pierwszym dopasowaniu pozwala znaleźć skrajny lewy punkt podziału.
Odczytujesz tablicę dwa razy: raz, aby obliczyć sumę całkowitą, i raz podczas skanowania, więc złożoność czasowa wynosi O(n). Przechowywane są tylko dwie liczby, więc dodatkowa złożoność pamięciowa wynosi O(1).
Algorytm
- Dodaj wszystkie wartości do
total. - Ustaw
leftna 0. - Dla każdego indeksu
i, jeślileftjest równetotal - left - nums[i], zwróći. - W przeciwnym razie dodaj
nums[i]dolefti przejdź dalej. - Jeśli pętla się zakończy, zwróć -1.
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
Pułapki i przypadki brzegowe
Większość błędnych odpowiedzi umieszcza wartość pivota po jednej ze stron albo pomija indeks skrajny.
- Dodawanie
nums[i]do sumy po lewej stronie przed porównaniem. Lewa strona uwzględnia wtedy wartość pivota, a dla[3, 1, 5, 2, 2]nie zostaje już znaleziony indeks 2. - Obliczanie prawej strony jako
total - left. Wtedynums[i]jest zaliczane do prawej strony; odejmij je również. - Pomijanie indeksu 0 lub ostatniego indeksu. Każdy z nich może być pivotem, ponieważ suma pustej strony wynosi 0.
[1, -1, 1]zwraca 0, a[4, -4, 9]zwraca 2. - Zwracanie ostatniego dopasowania zamiast pierwszego. W przypadku
[0, 0, 0]każdy indeks równoważy obie strony, a odpowiedzią jest 0. - Używanie dwóch wskaźników, które przesuwają się do środka z obu końców i powiększają mniejszą stronę. Działa to tylko wtedy, gdy każda wartość jest nieujemna; tutaj wartości sięgają -1000, więc suma strony może się zmniejszać, gdy dodajesz do niej kolejne wartości.
- Zapominanie, że tablice w Lua i R zaczynają się od 1. Zwróć
i-1, aby odpowiedzią był indeks liczony od 0.
Najczęstsze pytania4
Jaka jest złożoność czasowa funkcji Find Pivot Index?
Rozwiązanie z sumą całkowitą i sumą bieżącą działa w czasie O(n): jeden przebieg, aby zsumować tablicę, i jeden przebieg, aby ją przeszukać. Wykorzystuje dodatkową przestrzeń O(1). Ponowne obliczanie obu stron przy każdym indeksie zajmuje natomiast czas O(n²).
Dlaczego prawa suma jest równa całości minus lewa suma minus nums[i]?
Każda wartość tablicy znajduje się dokładnie w jednym z trzech miejsc: na lewo od i, na pozycji i albo na prawo od i. Ich sumy składają się na całość, więc suma po prawej stronie to suma całkowita pomniejszona o dwie pozostałe części. Dzięki temu możesz sprawdzić indeks bez sumowania wartości po prawej stronie.
Czy zadanie „Find Pivot Index” można rozwiązać za pomocą dwóch wskaźników?
Nie zawsze. Skanowanie dwoma wskaźnikami, które zawsze rozszerza mniejszą stronę, zakłada, że dodanie wartości powiększa stronę, co przestaje działać, gdy tylko wartości mogą być ujemne: strona może się zmniejszyć, mimo że ją rozszerzasz, więc podczas skanowania wskaźnik może minąć właściwy punkt podziału. Metoda sumy narastającej nie zakłada niczego na temat znaków i sprawdza każdy indeks.
Jaki jest indeks przestawienia tablicy zawierającej jeden element?
Wynik to 0. Obie strony jedynego elementu są puste, a suma pustej strony wynosi 0, więc obie strony są równe. Rozwiązanie z bieżącą sumą zwraca 0 przy pierwszym porównaniu: lewa strona wynosi 0, a suma całkowita minus 0 minus wartość również wynosi 0.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def pivotIndex(nums):
# Napisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
nums = [3, 1, 5, 2, 2]
Oczekiwane
2