Find Pivot Index

Q: Find Pivot Index'in zaman karmaşıklığı nedir?

Toplam ve birikimli toplam çözümü O(n) zamanda çalışır: diziyi toplamak için bir geçiş ve diziyi taramak için bir geçiş. O(1) ek alan kullanır. Her indekste her iki tarafı yeniden hesaplamak ise O(n²) zaman alır.

Q: Sağ toplam neden toplam eksi sol eksi nums[i] değerine eşittir?

Dizinin her değeri tam olarak üç yerden birindedir: i indeksinin solunda, i indeksinde ya da i indeksinin sağında. Bu değerlerin toplamları toplam değeri verir; dolayısıyla sağ tarafın toplamı, diğer iki bölüm çıkarıldığında kalan toplamdır. Böylece sağ tarafı hiçbir zaman toplamanıza gerek kalmadan bir indeksi kontrol edebilirsiniz.

KolayÖnek toplamı

+10

Bir tamsayı dizisi olan nums veriliyor. Dengeleme indeksi, solundaki değerlerin toplamının sağındaki değerlerin toplamına eşit olduğu indekstir. Dengeleme indeksindeki değer hiçbir tarafa dahil değildir ve hiç değer içermeyen bir tarafın toplamı 0'dır.

En soldaki dengeleme indeksini döndürün veya hiçbir indeks dengeleme indeksi değilse -1 döndürün.

Fonksiyon

pivotIndex(nums: integer-array) → integer

numsinteger-array: dengelemek için tam sayı dizisi
Döndürürinteger: En soldaki pivot indeksi; yoksa -1

Kısıtlar

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Örnekler

Girdi: nums = [3, 1, 5, 2, 2]
Çıktı: 2
Açıklama: İndeks 2'de sol taraf 3 + 1 = 4, sağ taraf ise 2 + 2 = 4 olur. İndeks 0 ve indeks 1 dengelenmez (0'a karşı sol taraf 0, 10'a karşı sol taraf 3), bu nedenle 2 en soldaki pivot'tur.

Girdi: nums = [1, 2, 3]
Çıktı: -1
Açıklama: Üç aday sırasıyla 5'e karşı 0, 3'e karşı 1 ve 0'a karşı 3 veriyor. Hiçbir indeks dengelenmediğinden yanıt -1.

Gönderirken +17 gizli test

Ek soru

Önce toplamı hesaplamadan ve her değeri yalnızca bir kez okuyarak en soldaki pivotu bulabilir misin? Bunun bellek maliyeti nedir?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir indeksi kontrol etmek için iki toplam gerekir, ancak bunları her indekste yeniden hesaplamak, iş yükünün uzunluğun karesiyle büyümesine neden olur. Çözüm, yeniden hesaplamayı bırakmaktır: sol toplam her adımda bir değer artar, sağ toplam ise toplamdan geriye kalandır. Toplamı bulmak için yapılan bir geçiş ve devam eden sol toplamla yapılan ikinci bir geçiş, bellekte iki sayı tutarak en soldaki pivotu bulur.

Her indekste her iki tarafı da toplayın

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Tanımı izleyin. Her i indeksi için, öncesindeki değerleri toplayın, sonrasındaki değerleri toplayın ve karşılaştırın. İki toplamın eşleştiği ilk indeks yanıttır; çünkü indeksleri soldan sağa denersiniz.

Kenarlar kendi kendine halledilir. 0 indeksinde sol döngü sıfır kez çalışır, dolayısıyla sol toplam 0'dır; son indekste sağ döngü sıfır kez çalışır. [4, -4, 9] değerinin 2 döndürmesinin nedeni budur.

Sorun maliyettir. Her indeks, diğer n-1 değeri toplar; bu yüzden toplam iş yaklaşık n² toplama işlemidir. 10.000 değerde bu, 100 milyon toplama işlemine yakındır ve bunların çoğu, yalnızca bir indeks önce hesapladığınız toplamları tekrarlar.

Algoritma

nums dizisinin her indeksi üzerinde i ile döngü oluştur.
Sol toplam olarak nums[0] ile nums[i-1] arasındaki değerleri topla.
Sağ toplam olarak nums[i+1] ile son değer arasındaki değerleri topla.
İki toplam eşitse i değerini döndür.
Hiçbir indeks eşleşmezse -1 döndür.

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 -1

Önek toplam dizisi

Sezgi

Kaba kuvvet yöntemi, dizideki ardışık değerlerin toplamlarını tekrar tekrar hesaplar. Önek toplam dizisi bu işi bir kez yapar. prefix[k], ilk k değerin toplamı olsun; burada prefix[0] = 0. [3, 1, 5, 2, 2] için bu dizi [0, 3, 4, 9, 11, 13] olur.

Artık herhangi bir ardışık değer grubunun toplamı, iki elemanın farkıdır. i indeksinin sol tarafı ilk i değerdir; dolayısıyla prefix[i] olur. Sağ taraf ise nums[i] değerinden sonraki her şeydir; bu da prefix[n] - prefix[i+1] olur. 2 indeksinde solda 4, sağda ise 13 - 9 = 4 elde edilir; bu bir dengelenme indeksidir.

Diziyi oluşturmak tek geçiş alır ve her kontrol sabit zaman alır; dolayısıyla aramanın tamamı O(n) olur. Bunun bedeli, bellekte n+1 fazladan sayı tutmaktır.

Algoritma

n+1 uzunluğunda bir prefix oluştur ve prefix[0] = 0 olarak ayarla.
Şu şekilde doldur: prefix[k+1] = prefix[k] + nums[k].
Her i indeksi için sol toplamı prefix[i], sağ toplamı ise prefix[n] - prefix[i+1] olarak oku.
Eşit oldukları ilk i değerini döndür; döngüden sonra eşitlik yoksa -1 döndür.

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 -1

Toplam ve biriken sol toplam

Sezgi

Önceki yaklaşımın hangi önek değerlerini okuduğuna bak. i indeksinde prefix[i], prefix[i+1] ve prefix[n] gerekir. Sonuncusu toplamdır ve hiç değişmez; diğer ikisi ise diziyi bir kez baştan sona dolaşsaydın elde edeceğin kümülatif toplamdır. Bu yüzden dizinin tamamı yerine toplamı ve soldan gelen tek bir kümülatif toplamı tutabilirsin.

Her değer solda, pivotta ya da sağdadır. Bu nedenle sağ toplam, toplamdan sol toplam ve nums[i] çıkarılarak bulunur. [3, 1, 5, 2, 2] için toplam 13'tür. 0 indeksinde sol toplam 0, sağ toplam ise 13 - 0 - 3 = 10'dur. 1 indeksinde sol toplam 3, sağ toplam 9'dur. 2 indeksinde sol toplam 4, sağ toplam 13 - 4 - 5 = 4 olduğundan 2'yi döndürürsün.

Döngü içindeki işlem sırası önemlidir. Önce karşılaştır, ardından nums[i] değerini sol toplama ekle; böylece sol toplam, sınadığın indeksteki değeri hiçbir zaman içermez. İlk eşleşmede döndürmek en soldaki pivotu verir.

Diziyi iki kez okursun: bir kez toplamı bulmak, bir kez de taramak için. Bu yüzden zaman karmaşıklığı O(n)'dir. Yalnızca iki sayı saklanır, bu nedenle ek alan karmaşıklığı O(1)'dir.

Algoritma

Her değeri total içine ekle.
left değerini 0 olarak ayarla.
Her i indeksi için, left değeri total - left - nums[i] değerine eşitse i değerini döndür.
Aksi takdirde nums[i] değerini left değerine ekle ve devam et.
Döngü sona ererse -1 döndür.

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

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu pivotun kendi değerini bir tarafa ekler veya bir kenar indeksini atlar.

Karşılaştırmadan önce nums[i] değerini sol toplama eklemek. Böylece sol taraf pivot değerini de içerir ve [3, 1, 5, 2, 2] artık 2 indeksini bulamaz.
Sağ tarafı total - left olarak hesaplamak. Bu, nums[i] değerini sağ tarafta sayar; onu da çıkarın.
0 indeksini veya son indeksi atlamak. Boş bir tarafın toplamı 0 olduğundan, her ikisi de pivot olabilir. [1, -1, 1] 0, [4, -4, 9] ise 2 döndürür.
İlk eşleşme yerine son eşleşmeyi döndürmek. [0, 0, 0] dizisinde her indeks dengeyi sağlar ve yanıt 0'dır.
Her iki uçtan içeri doğru ilerleyen ve küçük tarafı büyüten iki işaretçi kullanmak. Bu yalnızca tüm değerler negatif olmadığında işe yarar; burada değerler -1000'e kadar düşer, dolayısıyla bir taraf büyürken küçülebilir.
Lua ve R dizilerinin 1'den başladığını unutmak. Yanıtı 0 tabanlı indeks olarak vermek için i-1 döndürün.

Sıkça sorulan sorular4

Find Pivot Index'in zaman karmaşıklığı nedir?

Toplam ve birikimli toplam çözümü O(n) zamanda çalışır: diziyi toplamak için bir geçiş ve diziyi taramak için bir geçiş. O(1) ek alan kullanır. Her indekste her iki tarafı yeniden hesaplamak ise O(n²) zaman alır.

Sağ toplam neden toplam eksi sol eksi nums[i] değerine eşittir?

Dizinin her değeri tam olarak üç yerden birindedir: i indeksinin solunda, i indeksinde ya da i indeksinin sağında. Bu değerlerin toplamları toplam değeri verir; dolayısıyla sağ tarafın toplamı, diğer iki bölüm çıkarıldığında kalan toplamdır. Böylece sağ tarafı hiçbir zaman toplamanıza gerek kalmadan bir indeksi kontrol edebilirsiniz.

Pivot İndeksi Bulma, iki işaretçiyle çözülebilir mi?

Güvenilir bir şekilde değil. Her zaman daha küçük tarafı büyüten iki işaretçili bir tarama, bir değer eklemenin bir tarafı büyüttüğünü varsayar; değerler negatif olabildiğinde bu varsayım geçersiz olur: bir tarafı büyütürken küçültebilirsiniz, bu yüzden tarama bir işaretçiyi gerçek pivotun ötesine taşıyabilir. Biriken toplam yöntemi işaretlerin pozitif ya da negatif olduğu konusunda hiçbir varsayımda bulunmaz ve her indeksi kontrol eder.

Tek elemanlı bir dizinin pivot indeksi nedir?

Sonuç 0'dır. Tek elemanın her iki tarafı da boştur ve boş bir tarafın toplamı 0 olduğundan, iki taraf eşittir. Çalışan toplam çözümü ilk karşılaştırmasında 0 döndürür: sol taraf 0'dır ve toplamdan 0 ile değer çıkarıldığında da 0 elde edilir.

Python

def pivotIndex(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [3, 1, 5, 2, 2]

Beklenen

Find Pivot Index

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her indekste her iki tarafı da toplayın

Önek toplam dizisi

Toplam ve biriken sol toplam

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler