First Unique Character in a String

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

Harfleri saymak ve ardından dizeyi taramak, her biri n adım süren iki geçiştir; bu nedenle zaman karmaşıklığı O(n) 'dir. 26 sayaç, uzunluk ne olursa olsun aynı miktarda yer kaplar; bu da ek alanı O(1) yapar.

KolayHashing

+10

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

Fonksiyon

firstUniqChar(s: string) → integer

sstring: aranacak dize, yalnızca küçük harfler
Döndürürinteger: Yalnızca 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 harfleri iki kez, d üç kez ve e bir kez, 8. dizinde görünür. Ancak y de bir kez, 4. dizinde görünür ve ilk sırada geldiği için cevap 4'tür.

Girdi: s = "swiss"
Çıktı: 1
Açıklama: swiss içinde s harfi üç kez görünür. 1. indeksteki w harfi bir kez görünür; 2. indeksteki i harfi de öyle. İlk gelen kazandığı için cevap 1'dir.

Girdi: s = "aabbcc"
Çıktı: -1
Açıklama: aabbcc içindeki her harf iki kez geçtiğinden hiçbir karakter benzersiz değildir ve yanıt -1'dir.

Gönderirken +17 gizli test

Ek soru

Karakterler bir akıştan teker teker gelir ve her birinden sonra o ana kadar karşılaşılan ilk benzersiz karakteri bildirmen gerekir. Yanıtı nasıl güncel tutardın?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Karşına çıktığında benzersiz görünen bir harf, dizenin en sonunda tekrarlanabilir; bu yüzden soldan sağa tek bir göz gezdirmek 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 anlayabilirsin.

Her harfin ikinci bir kopyasını ara

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

Sezgi

Soldan başlayarak konumları sırayla incele. i konumu için, dizenin tamamını tarayarak aynı harfe sahip başka bir j konumu ara. Böyle bir konum yoksa s[i] tektir ve soldan ilerlediğin için ilk tek harftir: i değerini döndür. coddycode içinde 0'dan 3'e kadar olan konumların her biri harfin başka bir kopyasını bulur; 4. konumdaki y ise bulamaz.

Tarama, i konumundan önceki ve sonraki karakterleri de kapsayacak şekilde dizenin tamamını incelemelidir. Dizede daha önce bulunan bir kopya, harfi daha sonra bulunan bir kopya kadar geçersiz kılar.

İlk kopyada durmak çoğu dizgede işe yarar, ancak hepsinde değil. Her harf, 2000 tane a, ardından 2000 tane b ve bu şekilde devam eden uzun bir blokta yer alıyorsa, her harfin taraması kopyasını bulmadan önce kendisinden önceki tüm blokları geçer. n = 5 × 10^4 için bu, bir milyardan fazla karşılaştırma demektir; en büyük testler için fazla yavaştır.

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 indeksin bir kopyası varsa -1 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

Kaba kuvvet yaklaşımı, her konum için yeniden "bu harf başka bir yerde geçiyor mu?" diye sorar. Bunun yerine sayımı bir kez yap. Yalnızca 26 harf vardır; bu nedenle 26 sayaçtan oluşan bir dizi tüm sayımları tutar: a için 0. indeks ve z için 25. indeks. Bir harfin indeksi, karakter kodundan a harfinin kodunun çıkarılmasıyla bulunur.

İlk geçiş sayaçları doldurur. coddycode için sayaç değerleri şöyledir: c: 2, o: 2, d: 3, y: 1, e: 1. İkinci geçiş, soldan başlayarak dizgede ilerler ve harfin sayımının 1 olduğu ilk konumda durur. Bu, 4. indeksteki y harfidir. Soru alfabenin ilk harfiyle değil, ilk konumla ilgili olduğu için ikinci geçiş 26 sayacı değil, dizgeyi taramalıdır.

Her iki geçiş de dizgeyi bir kez okur; dolayısıyla zaman karmaşıklığı O(n) olur. Dizge ne kadar uzun olursa olsun sayaç sayısı 26 olarak kalır; dolayısıyla ek alan karmaşıklığı O(1) olur.

Algoritma

26 sıfırdan oluşan bir dizi oluştur.
s içindeki her harf için sayacını 1 artır.
s üzerinde 0 indeksinden başlayarak yeniden ilerle. Harfin sayısı 1 olan ilk indeksi döndür.
İlerleme 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

Hataların çoğu çok erken karar vermekten veya ikinci geçişte yanlış şeyi dolaşmaktan kaynaklanır.

Yalnızca i konumundan önceki harfleri kontrol etmek. abca dizisinde ilk a harfinden önce başka bir kopyası yoktur, ancak bu harf benzersiz değildir.
İkinci geçişte dizi yerine sayaç dizisini dolaşmak. ba için 1'e eşit olan ilk sayaç a harfine aittir, ancak yanıt indeks 0, yani b harfidir.
İndeks yerine harfi döndürmek veya indeksi 1 tabanlı olarak döndürmek. Lua ve R saymaya 1'den başlar, bu nedenle döndürmeden önce 1 çıkarın.
-1 durumunu unutmak. aabbcc gibi bir dizgede benzersiz harf yoktur ve döngüden sonra işlev yine de bir değer döndürmelidir.
Sayaçları ham karakter koduyla indekslemek. a 97'dir; bu, 26 elemanlı bir dizinin sınırını çok aşar. Önce a harfinin kodunu çıkarın.

Sıkça sorulan sorular4

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

Harfleri saymak ve ardından dizeyi taramak, her biri n adım süren iki geçiştir; bu nedenle zaman karmaşıklığı O(n)'dir. 26 sayaç, uzunluk ne olursa olsun aynı miktarda yer kaplar; bu da ek alanı O(1) yapar.

Karakter dizgesini tek geçişte çözebilir misin?

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

Harfleri saymak için bir hash map mi yoksa bir dizi mi kullanmalısınız?

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

Neden ikinci geçiş sayımların üzerinden değil de dizenin üzerinden geçiyor?

Sayımlar yalnızca hangi harflerin benzersiz olduğunu söyler, nerede bulunduklarını değil. Yanıt, dizgede ilk sırada gelen benzersiz harftir; bu yüzden dizgeyi sırayla taramalı ve harfin sayımının 1 olduğu ilk konumda durmalısın.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "coddycode"

Beklenen