İlk benzersiz karakter
Görev tanımı
Problem
Bir metin parçası verildiğinde, bütün metinde tam olarak bir kez görünen ilk karakterin konumunu bul. Konumlar sıfırdan sayılır. Her karakter birden fazla kez görünüyorsa -1 döndür.
Örnekler
Input: text = "reference"
Output: 2
Neden: r ve e ikisi de sonra tekrar ediyor, yani tek başına duran ilk karakter f
Input: text = "aabb"
Output: -1
Neden: her karakterin bir ikizi var
Input: text = ""
Output: -1
Neden: edge case: bildirilecek karakter yok
İpuçları
0 / 3
Bir karakterin benzersiz olup olmadığı, ondan sonra gelenler dahil bütün metne bağlı; yani ilk görüşte soldan sağa tek bir karar verilemez.
İki soruyu ayır: her karakter ne sıklıkla geçiyor ve hangi konum önce geliyor. İlk soru ikincisi sorulmadan önce tamamen cevaplanabilir.
Her karakteri tek geçişte say. Sonra metni sırayla yeniden dolaş ve sayısı bir olan ilk karakterin konumunu döndür. Bir isabet olmadan sona ulaşmak cevabın -1 olduğu anlamına gelir.
- Hedef zaman
- O(n)
- Hedef alan
- O(k)
Çözüm
Benzersizlik tek bir ileri geçiş sırasında belirlenemez, çünkü bir kez görülen bir karakter sonra yine tekrar edebilir. İki geçiş bunu temiz biçimde çözer: ilki her karakterin bir sayımını kurar, ikincisi de metni sırayla dolaşıp sayımı bir olan ilk karakterde durur. Sayımı değil metni dolaşmak, cevabın keyfi bir konum değil ilk konum olmasını sağlar. Zaman O(n), farklı karakterler için alan O(k).
from collections import Counter
def first_unique_index(text):
counts = Counter(text) # one pass to tally every character
for i, ch in enumerate(text):
if counts[ch] == 1: # the earliest character with a tally of one
return i
return -1
print(first_unique_index("reference")) # -> 2
print(first_unique_index("aabb")) # -> -1
print(first_unique_index("")) # -> -1Kodda değil de fikirde mi takıldın? Frekans sayma bunu anlatıyor.