Find Peak Element

Q: Find Peak Element'ın zaman karmaşıklığı nedir?

İkili arama O(log n) zamanda ve O(1) alan kullanarak çalışır; 5000 değer için en fazla 13 adım sürer. Soldan ilerlemek O(n) zaman alır, çünkü düşüşü bulmadan önce her çifti okuyabilir.

Q: Birden fazla tepe noktası olduğunda ikili arama yine de çalışır mı?

Evet, komşular birbirinden farklı olduğu ve her iki ucun ötesindeki noktalar tüm değerlerden daha düşük sayıldığı sürece. En yüksek olanı değil, bir tepe döndürür. Bir yükseliş adımından sonra değerler en geç aralığın sonuna kadar düşüşe geçmelidir ve ilk dönüş bir tepe olduğundan, aramanın tuttuğu tarafta her zaman bir tepe bulunur.

Q: Tepe noktası her zaman en büyük değer midir?

Bu problemde evet: dizi tek bir tepe noktasına kadar yükselir ve sonra alçalır, dolayısıyla başka hiçbir değer daha büyük olamaz. Birden fazla tepe noktasının olduğu sürümde ise durum böyle değildir; çünkü her iki komşusundan da büyük olan herhangi bir değer tepe noktası sayılır. Aramanın maksimum değeri bulmak yerine komşuları karşılaştırmasının nedeni budur.

Ortaİkili arama

+10

nums dizisi önce yükselir, sonra düşer: bir indekse kadar her değer kendisinden önceki değerden büyüktür ve bu indeksten sonraki her değer kendisinden önceki değerden küçüktür. Her iki bölümden biri boş olabilir; bu nedenle dizi yalnızca yükselebilir veya yalnızca düşebilir. Dönüş indeksindeki değer tepedir; komşularının her birinden büyük olan tek değerdir.

Tepe değerinin indeksini O(log n) zamanda döndürün.

Fonksiyon

findPeakElement(nums: integer-array) → integer

numsinteger-array: değerler bir tepe noktasına yükselir ve ardından düşer
Döndürürinteger: tepenin indeksi

Kısıtlar

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] her geçerli i için.
nums bir indekse kadar kesin artar ve o indeksten sonra kesin azalır; dolayısıyla tam olarak bir tepe noktası vardır.

Örnekler

Girdi: nums = [2, 5, 9, 4, 1]
Çıktı: 2
Açıklama: Değerler 2, 5 ve 9 üzerinden yükselir, ardından 4 ve 1 üzerinden düşer. Dönüş noktası 9, indeks 2'dir.

Ek soru

Komşu hücrelerden hiçbirinin eşit olmadığı bir ızgarada, tepe bir hücrenin en fazla dört komşusundan daha büyük olmasıdır. Her hücreyi okumadan bir tepe bulabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Tek bir tepe olduğunda, tepe en büyük değerdir; bu nedenle tek bir geçişte O(n) içinde bulunur. O(log n) için nums[mid] ile nums[mid+1] değerlerini karşılaştır: mid noktasındaki eğim, tepenin hangi tarafında olduğunu gösterir; böylece her adımda aralığın yarısı elenebilir.

Değerler düşmeye başlayana kadar yürü

Sezgi

Zirveden önce her değer bir sonrakinden küçüktür ve zirveden itibaren her değer daha büyüktür. Bu yüzden zirve, nums[i] > nums[i+1] koşulunu sağlayan ilk i indeksidir veya dizi yalnızca yükseliyorsa son indekstir.

Zirve 5000 değerin sonunda olduğunda, yürüyüş 4999 karşılaştırma yapar; ikili arama ise 13 karşılaştırma gerektirir.

Algoritma

0'dan n-2'ye kadar i için, nums[i] ile nums[i+1]'i karşılaştır.
nums[i]'nin daha büyük olduğu ilk i değerinde, i'yi döndür.
Döngü bir düşüş olmadan sona ererse, n-1'i döndür.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

Eğim üzerinde ikili arama

Sezgi

Bir çifti, nums[mid] ve nums[mid+1] değerlerini okuyun. Yükselen bir adım, dizinin hâlâ yükseldiği anlamına gelir; bu dizide bu yalnızca zirveden önce gerçekleşir: zirve mid+1 konumundadır veya onun sağındadır. Alçalan bir adım, zirvede ya da zirveyi geçmiş olduğunuz anlamına gelir: zirve mid konumundadır veya onun solundadır.

Zirveyi her zaman içeren bir [lo, hi] aralığını koruyun. Yükselen bir adımda lo değerini mid+1 konumuna taşıyın. Alçalan bir adımda hi değerini mid konumuna taşıyın; zirve olabileceği için mid değerini aralıkta tutun. lo ile hi eşitlendiğinde geriye kalan tek indeks zirvedir. mid değerini aşağı yuvarlamak onun hi değerinden küçük kalmasını sağlar; böylece mid+1 her zaman vardır.

İlk örnekte, mid = 2 iken 9 > 4 görülür, bu yüzden hi = 2 olur; ardından mid = 1 iken 5 < 9 görülür, bu yüzden zirve olan lo = 2 olur. 5000 değer en fazla 13 adım gerektirir.

Algoritma

lo = 0 ve hi = n-1 değerlerini ayarla.
lo < hi olduğu sürece mid = lo + (hi - lo) / 2 değerini hesapla ve aşağı yuvarla.
nums[mid] < nums[mid+1] ise lo = mid + 1 değerini ayarla.
Aksi takdirde hi = mid değerini ayarla.
lo değerini döndür.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

Tuzaklar ve uç durumlar

Bir aşağı adımda hi = mid - 1 ayarlamak. [2, 5, 9, 4, 1] içinde ilk mid tepe noktasının kendisidir ve hi = 1 bu noktayı aralıktan çıkarır; arama 1 sonucunu döndürür.
mid değerini aşağı yuvarlarken nums[mid-1] ile karşılaştırmak. mid 0 olabilir; bu durumda sol komşu yoktur.
hi = n ile yarı açık aralık kullanmak. Böylece mid n-1 olabilir ve nums[mid+1] dizinin sonunun ötesini okur; tek bir değer için bu hemen gerçekleşir.
Lua ve R'de kaydırmayı unutmak. Yanıt hâlâ 0 tabanlı indekstir, bu nedenle i konumu i-1 olarak döndürülür.

Sıkça sorulan sorular3

Find Peak Element'ın zaman karmaşıklığı nedir?

İkili arama O(log n) zamanda ve O(1) alan kullanarak çalışır; 5000 değer için en fazla 13 adım sürer. Soldan ilerlemek O(n) zaman alır, çünkü düşüşü bulmadan önce her çifti okuyabilir.

Birden fazla tepe noktası olduğunda ikili arama yine de çalışır mı?

Evet, komşular birbirinden farklı olduğu ve her iki ucun ötesindeki noktalar tüm değerlerden daha düşük sayıldığı sürece. En yüksek olanı değil, bir tepe döndürür. Bir yükseliş adımından sonra değerler en geç aralığın sonuna kadar düşüşe geçmelidir ve ilk dönüş bir tepe olduğundan, aramanın tuttuğu tarafta her zaman bir tepe bulunur.

Tepe noktası her zaman en büyük değer midir?

Bu problemde evet: dizi tek bir tepe noktasına kadar yükselir ve sonra alçalır, dolayısıyla başka hiçbir değer daha büyük olamaz. Birden fazla tepe noktasının olduğu sürümde ise durum böyle değildir; çünkü her iki komşusundan da büyük olan herhangi bir değer tepe noktası sayılır. Aramanın maksimum değeri bulmak yerine komşuları karşılaştırmasının nedeni budur.

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

Test #1

Test #2

Test #3

Argüman

nums = [2, 5, 9, 4, 1]

Beklenen Çıktı