Leaders in an Array

+10

Bir tamsayı dizisi nums alırsın. Bir eleman, sağındaki her elemandan büyük veya eşit olduğunda lider sayılır. Son elemanın sağında hiçbir şey olmadığından, her zaman liderdir. Tüm liderleri, nums içinde soldan sağa göründükleri sırayla döndür.

Fonksiyon

leaders(nums: integer-array) → integer-array

numsinteger-array: aranacak tamsayı dizisi
Döndürürinteger-array: nums'un liderleri, soldan sağa

Kısıtlar

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

Örnekler

Girdi: nums = [12, 5, 9, 3, 6, 2]
Çıktı: [12, 9, 6, 2]
Açıklama: 2 en sonda, bu yüzden başa geçer. 6, ardından gelen 2'yi geçer; 9, 3'ü, 6'yı ve 2'yi geçer; 12 ise hepsini geçer. 5, 9'a; 3 ise 6'ya yenilir, bu yüzden cevap [12, 9, 6, 2] olur.

Ek soru

Değerler teker teker geliyor ve her birinden sonra şu ana kadarki liderleri bildirmeniz gerekiyorsa, her değer için amortize O(1) zamanda listeyi nasıl güncellersiniz?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Soldan okuduğunda, her öğe için son ekin baştan taranması gerekir. Bunun yerine sağdan ilerle: son ek hakkında bilmen gereken tek şey en büyük değeridir ve bunu tek bir değişkende tutabilirsin. Böylece O(n²) kontrolü tek geçişe dönüşür.

Sağdaki her şeyi kontrol et

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

Sezgi

Tanımı uygulayın: her i indeksi için sonraki elemanları tarayın ve nums[i] değerinden kesinlikle büyük olan ilk elemanda durun. Tarama sona ulaşırsa nums[i] liderdir. İndeksleri soldan sağa test edersiniz, böylece liderler sıralı olarak ortaya çıkar. [12, 5, 9, 3, 6, 2] dizisinde 5, 9'da durur ve 3, 6'da durur.

Maliyet, sona kadar devam eden taramalardan kaynaklanır. 24.999 eşit değerin ardından daha büyük tek bir değer gelirse, her eleman dizinin neredeyse tamamını dolaşır: yaklaşık 25.000 × 25.000 / 2, yani 3 × 10^8 karşılaştırmadan fazla.

Algoritma

Boş bir sonuç listesi oluştur.
Her i indeksi için j değerini i + 1 konumundan sona kadar tara.
Herhangi bir nums[j] değeri nums[i] değerinden büyükse dur: nums[i] bir lider değildir.
Böyle bir j yoksa nums[i] değerini sonuca ekle.
Sonucu döndür.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Sağdan başlayarak ilerleyen maksimum değerle tek geçiş

Sezgi

Sağdaki her eleman kadar büyük ya da daha büyük olmak, onların maksimumu kadar büyük ya da daha büyük olmakla aynıdır. Sağdan sola ilerlerken bu maksimumu güncel tutabilirsin. Son eleman öndedir ve maksimumu başlatır. Solundaki her eleman, maksimumdan büyük ya da ona eşitse öne geçer ve sonra yeni maksimum olur; aksi hâlde sağında daha büyük bir değer vardır.

[12, 5, 9, 3, 6, 2] için: 2 öne geçer, ardından 6, sonra 9 ve 12; 3 ve 5 ise maksimumun altında kalır. [2, 6, 9, 12] dizisini buldun; ters çevrilmiş hâli yanıttır.

Her eleman bir kez karşılaştırılır: O(n) zaman ve sonuç dışında O(1) ek alan. R sürümü, öne geçenleri bir logical(n) vektöründe işaretler; dolayısıyla ek alanı O(n)’dir.

Algoritma

Son elemanı result içine koy ve best değerini ona ayarla.
i değerini sondan ikinci indeksten 0'a kadar azalt.
nums[i] ≥ best ise nums[i] değerini result içine ekle ve best değerini buna ayarla.
Liderler soldan sağa okunacak şekilde result değerini ters çevir ve döndür.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Tuzaklar ve uç durumlar

Çalışan maksimumla karşılaştırırken > kullanmak, ≥ kullanmamak. [4, 7, 7, 1, 7] dizisinde her 7 liderdir, ancak katı bir karşılaştırma yalnızca sonuncuyu tutar.
Maksimumu son eleman yerine 0 olarak başlatmak. [-1, -5] ikisini de döndürmelidir, ancak 0 maksimumu bunları dışarıda bırakır.
Liderleri bulduğun sırayla döndürmek: [12, 9, 6, 2] yerine [2, 6, 9, 12].
Son elemanı zaten sonuca ekledikten sonra döngüyü son indexten başlatarak son elemanı iki kez eklemek.
Her elemanı yalnızca komşusuyla karşılaştırmak. [5, 3, 9] dizisinde 5, yanındaki 3'ten büyüktür, ancak 9 nedeniyle cevap [9] olur.

Sıkça sorulan sorular3

Dizideki liderleri bulmanın zaman karmaşıklığı nedir?

Sağdan tek geçişle O(n), çünkü her öğe o ana kadarki maksimumla bir kez karşılaştırılır. Her öğeyi sağındaki tüm öğelerle karşılaştırmak, örneğin tüm değerler eşit olduğunda, en kötü durumda O(n²) maliyetlidir.

Son öğe her zaman bir lider midir?

Evet. Bir lider, sağındaki her öğe kadar büyük veya daha büyük olmalıdır ve son öğenin sağında hiçbir öğe yoktur; bu nedenle kontrol edilecek bir şey olmadan koşul sağlanır.

Eşit değerler lider sayılır mı?

Burada evet: bir lider, sağındaki her öğeden büyük veya ona eşit olmalıdır; bu nedenle [4, 7, 7, 1, 7] dizisinde üç 7'nin tamamı liderdir. Bazı sürümlerde kesin olarak daha büyük olması istenir; bu durumda > ile karşılaştırın ve eşit değerlerden yalnızca sonuncusu lider olur.

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

Test #1

Test #2

Test #3

Argüman

nums = [12, 5, 9, 3, 6, 2]

Beklenen Çıktı

[12, 9, 6, 2]