Çoğunluk değeri
Görev tanımı
Problem
Bir listede tek bir değer bütün konumların yarısından fazlasını kaplıyor. O değeri döndür. Böyle bir değerin her zaman var olduğunu varsayabilirsin; yani hiçbir zaman başarısızlık bildirmen gerekmez ve liste asla boş değildir.
Örnekler
Input: nums = [3, 3, 4]
Output: 3
Neden: 3 üç hücrenin ikisini dolduruyor, bu yarıdan fazla
Input: nums = [2, 2, 1, 1, 2]
Output: 2
Neden: çoğunluk değerinin bir arada durması gerekmez
Input: nums = [9]
Output: 9
Neden: edge case: tek değer listenin yarısından fazlasına doğal olarak sahip
İpuçları
0 / 3
Her değeri bir map'te saymak işi çözer, ama bir değerin hücrelerin yarısından fazlasına sahip olduğu garantisi, tam bir sayımın ihtiyaç duyduğundan çok daha güçlü bir bilgi.
Çoğunluk değerinin her geçişinin başka bir şeyin bir geçişini götürdüğünü düşün. Yarıdan fazlasına sahip olduğu için bu götürmeden geriye her zaman bir şey kalır.
Bir aday ve bir fark sayacı taşı. Fark sıfıra düşünce mevcut elemanı yeni aday olarak al. Eleman adayla eşleşiyorsa farkı artır, eşleşmiyorsa azalt. Sonunda ayakta kalan aday cevaptır.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- one value fills more than half the positions
- the list is never empty
Çözüm
Çoğunluk değerinin her geçişini çoğunluk olmayan bir geçişle eşlemek ikisini birden götürür; çoğunluk hücrelerin yarısından fazlasına sahip olduğu için tamamen götürülemez. Tek bir aday ve bir fark sayacı, başka hiçbir şey saklamadan bu eşleşmeyi taklit eder: farkın sıfıra inmesi önceki adayın tamamen eşlendiği anlamına gelir, bu yüzden sonraki eleman yeni bir tur başlatır. Tek geçişle zaman O(n), alan O(1).
def majority_value(nums):
candidate = None
lead = 0 # how far the candidate is ahead
for x in nums:
if lead == 0: # the previous candidate was fully cancelled
candidate = x
lead += 1 if x == candidate else -1
return candidate
print(majority_value([3, 3, 4])) # -> 3
print(majority_value([2, 2, 1, 1, 2])) # -> 2
print(majority_value([9])) # -> 9Kodda değil de fikirde mi takıldın? Çoğunluk elemanı bunu anlatıyor.