First Unique Character in a String

Q: Bir Dizgedeki İlk Benzersiz Karakterin zaman karmaşıklığı nedir?

Harfleri saymak ve ardından dizgeyi taramak, n adımlı iki geçiştir; dolayısıyla süre O(n) 'dir. 26 sayaç, uzunluk ne olursa olsun aynı alanı kaplar; bu nedenle ek alan O(1) 'dir.

KolayHashing

+10

Küçük İngilizce harflerden oluşan bir s dizgesi veriliyor. Dizgenin tamamında tam olarak bir kez geçen ilk karakteri bulun ve 0'dan başlayarak indeksini döndürün. Her karakter birden fazla kez geçiyorsa -1 döndürün.

Fonksiyon

firstUniqChar(s: string) → integer

sstring: aranacak dize, yalnızca küçük harfler
Döndürürinteger: tam olarak bir kez görünen ilk harfin indeksi; yoksa -1

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s yalnızca küçük İngilizce harfler (a ile z arası) içerir.

Örnekler

Girdi: s = "coddycode"
Çıktı: 4
Açıklama: coddycode içinde c ve o iki kez, d ise üç kez görünür. Hem y (indeks 4) hem de e (indeks 8) bir kez görünür ve önce y geldiği için cevap 4'tür.

Girdi: s = "swiss"
Çıktı: 1
Açıklama: s harfi üç kez geçer. Hem 1. indeksteki w hem de 2. indeksteki i bir kez geçer ve w önce gelir.

Girdi: s = "aabbcc"
Çıktı: -1
Açıklama: aabbcc içindeki her harf iki kez geçtiği için cevap -1 olur.

Ek soru

Karakterler bir akıştan teker teker gelir. Her birinden sonra şimdiye kadarki ilk benzersiz karakteri nasıl bildirirdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Ona ulaştığında benzersiz görünen bir harf, dizenin en sonunda tekrar edebilir; bu yüzden soldan sağa tek bir bakış yeterli değildir. Önce her harfi say, ardından ikinci geçişte her konumun benzersiz bir harf içerip içermediğini sabit zamanda belirleyebilirsin.

Her harfin ikinci bir kopyasını ara

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

Sezgi

Soldan başlayarak her konum için, aynı harfin bulunduğu başka bir konum olup olmadığını bulmak üzere dizenin tamamını tara. Her iki tarafı da tara: Daha önceki bir kopya da sonraki bir kopya kadar harfi geçersiz kılar. Kopyası olmayan ilk konum cevaptır. coddycode içinde 0 ile 3 arasındaki konumların her biri bir kopya bulur ve 4. indisteki y hiçbir kopya bulmaz.

Her harf 2000 a, ardından 2000 b ve bu şekilde devam eden tek bir uzun dizide yer alıyorsa, ilk kopyada durmak işe yaramaz: her tarama, önceki dizilerin tümünü geçer. n = 5 × 10^4 değerinde bu, bir milyardan fazla karşılaştırma demektir.

Algoritma

Soldan sağa her i indeksi için:
i dışındaki tüm j indekslerini tara ve s[j] değerinin s[i] değerine eşit olduğu ilk indekste dur.
Böyle bir j yoksa i değerini döndür.
Her indeks için bir kopya bulunduysa -1 değerini döndür.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

Harfleri sayın, ardından tarayın

Sezgi

Her konum için yeniden arama yapmak yerine her harfi bir kez sayın. Yalnızca 26 harf vardır, bu nedenle 26 sayaç tüm sayımları tutar ve harfin kodundan a'nın kodu çıkarılarak indekslenir.

İlk geçiş sayaçları doldurur; coddycode için yalnızca y ve e 1 değerinde kalır. İkinci geçiş dizgeyi soldan dolaşır ve sayısı 1 olan ilk harfte, 4. indeksteki y'de durur. n adımlık iki geçiş O(n) zaman alır ve 26 sayaç, uzunluk ne olursa olsun O(1) alan kullanır.

Algoritma

26 sıfırdan oluşan bir dizi oluştur.
s'deki her harf için sayacını 1 artır.
s'yi 0 indeksinden başlayarak tekrar dolaş. Sayısı 1 olan ilk harfin indeksini döndür.
Dolaşma sona ererse -1 döndür.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

Tuzaklar ve uç durumlar

Yalnızca i konumundan önceki harfleri kontrol etmek. abca içinde ilk a harfinden önce aynı harften başka bir tane yoktur, ancak bu harf benzersiz değildir.
İkinci geçişte dize yerine sayaç dizisi üzerinde ilerlemek. ba için 1'e eşit ilk sayaç a harfine aittir, ancak yanıt 0 indeksidir.
Sayaçları ham karakter koduyla indekslemek. a 97 değerindedir; bu da 26 sayaçlık dizinin sınırlarının çok ötesindedir.
İndeksi yerine harfi döndürmek ya da Lua veya R'de 1 tabanlı bir indeks döndürmek.

Sıkça sorulan sorular3

Bir Dizgedeki İlk Benzersiz Karakterin zaman karmaşıklığı nedir?

Harfleri saymak ve ardından dizgeyi taramak, n adımlı iki geçiştir; dolayısıyla süre O(n)'dir. 26 sayaç, uzunluk ne olursa olsun aynı alanı kaplar; bu nedenle ek alan O(1)'dir.

String üzerinde tek geçişte çözebilir misin?

Evet. Tek geçişte, her harf için ilk göründüğü indeksi saklayın veya tekrar göründüğünde onu tekrarlanmış olarak işaretleyin. Ardından, bir kez görünen 26 harf arasındaki en küçük indeksi alın. Dize bir kez okunur ve son kontrol 26 adım sürer.

Harfleri saymak için karma eşleme mi yoksa dizi mi kullanmalısınız?

Yalnızca küçük harfler kullanıldığında, 26 sayaçtan oluşan bir dizi daha küçük ve daha hızlıdır. Dize Unicode metni gibi herhangi bir karakteri içerebiliyorsa doğru tercih bir karma haritadır. Algoritma aynı kalır: say, ardından dizeyi tara.

def firstUniqChar(s):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

s = "coddycode"

Beklenen Çıktı