Tekrar eden değer kontrolü
Görev tanımı
Problem
Bir değer listesi verildiğinde, herhangi bir değerin birden fazla kez görünüp görünmediğine karar ver. Listenin herhangi bir yerinde en az bir değer tekrar ediyorsa true, her değer benzersizse false döndür. Tekrarların yan yana olması gerekmez.
Örnekler
Input: items = [4, 1, 9, 1]
Output: True
Neden: 1 değeri iki farklı konumda görünüyor
Input: items = [4, 1, 9]
Output: False
Neden: üç değerin üçü de farklı
Input: items = []
Output: False
Neden: edge case: boş liste tekrar içeremez
İpuçları
0 / 3
Her çifti karşılaştırmak soruyu cevaplar ama gerekenden çok daha fazla iş yapar. Listeyi bir kez okurken neyi not alacağını düşün.
Her elemandaki tek soru, o değerle daha önce karşılaşıp karşılaşmadığın; bu bir arama değil, bir üyelik testi.
Zaten görülen değerlerden bir koleksiyon tut. Her eleman için önce üyeliği kontrol et; oradaysa hemen olumlu cevapla dur, değilse ekle ve devam et. Sona ulaşmak her şeyin benzersiz olduğu anlamına gelir.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Çözüm
Zaten görülen değerlerden oluşan bir küme (set), tekrar eden değer sorusunu sabit zamanlı bir üyelik testine çevirir. Listeyi bir kez dolaşıp eklemeden önce test etmek, cevabın taramayı bitirmeden ikinci kopya göründüğü anda döndürülmesi demektir. Zaman ortalamada O(n), bütün değerler farklı olduğunda en kötü durumda alan O(n).
def has_repeat(items):
seen = set() # values met so far
for x in items:
if x in seen: # this exact value already appeared
return True
seen.add(x)
return False # the scan finished without a collision
print(has_repeat([4, 1, 9, 1])) # -> True
print(has_repeat([4, 1, 9])) # -> False
print(has_repeat([])) # -> FalseKodda değil de fikirde mi takıldın? Frekans sayma bunu anlatıyor.