Denge noktası indeksi
Görev tanımı
Problem
Negatif olabilen tam sayılardan oluşan bir liste verildiğinde, kendisi hariç solundaki değerlerin toplamı, sağındakilerin toplamına eşit olan bir konum bul. Boş taraf sıfır sayılır. Böyle en soldaki indeksi döndür, yoksa -1 döndür.
Örnekler
Input: values = [2, 7, 1, 5, 4]
Output: 2
Neden: 2 indeksinin solunda 2 + 7 = 9, sağında 5 + 4 = 9
Input: values = [1, 2, 3]
Output: -1
Neden: listeyi eşit iki tarafa bölen bir indeks yok
Input: values = [5]
Output: 0
Neden: edge case: tek değerin iki tarafı da boş ve toplamları 0
İpuçları
0 / 3
Her indekste iki tarafı sıfırdan toplamak aynı toplamaları tekrar tekrar yapar; bu da bütün kontrolü karesel yapar.
Bütün listenin toplamını bildiğin anda, herhangi bir indeksteki sağ taraf, sol taraf ve o indeksteki değerle hesaplanabilir.
Listeyi bir kez topla. Sonra kümülatif bir sol toplamla dolaş: sağ toplam, genel toplam eksi sol toplam eksi mevcut değerdir. Eşit oldukları ilk indeksi döndür; devam etmeden önce mevcut değeri sol toplama ekle.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- values may be negative
Çözüm
Bir geçiş genel toplamı hesaplar, ikinci geçiş de geride kalan her şeyin kümülatif toplamını tutar. Her indekste sağ taraf, toplamdan sol taraf ve mevcut değer çıkarıldıktan sonra kalandır; bu yüzden her kontrol O(n) yerine O(1)'dir. İlk eşleşme döndürülür, bu da onu en soldaki yapar. Zaman O(n), ek alan O(1).
def balance_point(values):
total = sum(values)
left = 0
for i, v in enumerate(values):
right = total - left - v # everything after index i
if left == right:
return i
left += v
return -1
print(balance_point([2, 7, 1, 5, 4])) # -> 2
print(balance_point([1, 2, 3])) # -> -1
print(balance_point([5])) # -> 0Kodda değil de fikirde mi takıldın? O(1) ve O(n) bunu anlatıyor.