Contains Duplicate

Q: Contains Duplicate'ın zaman karmaşıklığı nedir?

Küme (hash set) çözümü ortalama olarak O(n) zamanda çalışır ve O(n) ek alan kullanır. Önce sıralamak O(n log n) zaman alır ve girdiyi yeniden sıralayabiliyorsanız ek dizi gerektirmez. Her çifti karşılaştırmak O(n²) zaman alır.

Q: Ekstra alan kullanmadan Contains Duplicate problemini çözebilir misin?

Evet, diziyi yeniden sıralamanıza izin veriliyorsa: diziyi yerinde sıralayın ve her değeri komşusuyla karşılaştırın. Böylece O(n) küme yerine O(n log n) zaman kullanılır. Yeniden sıralama yapmadan ve ek bellek kullanmadan geriye kalan tek seçenek O(n²) ikili kontroldür.

Q: Bir hash kümesi kontrolü neden hızlı yapar?

Bir karma kümesi değerleri karmalarına göre saklar; bu nedenle bir değeri içerip içermediğini sormak, tarama yapmak yerine ortalama olarak sabit zaman alır. Her öğe için bir arama ve bir ekleme işlemi gerekir; bu da tüm geçişi doğrusal zamanlı hâle getirir.

KolayHashing

+10

Bir tamsayı dizisi nums alırsın. Herhangi bir değer en az iki kez görünüyorsa true, tüm değerler farklıysa false döndür.

Fonksiyon

containsDuplicate(nums: integer-array) → boolean

numsinteger-array: kontrol edilecek tam sayılar
Döndürürboolean: herhangi bir değer en az iki kez görünüyorsa true, aksi takdirde false

Kısıtlar

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Örnekler

Girdi: nums = [3, 1, 4, 1, 5]
Çıktı: true
Açıklama: 1 değeri 1. indekste ve tekrar 3. indekste görünür, bu nedenle cevap true olur.

Girdi: nums = [2, 7, 1, 8]
Çıktı: false
Açıklama: 2, 7, 1 ve 8 dört farklı değerdir, bu yüzden hiçbir değer tekrarlanmaz.

Girdi: nums = [-4, 4, 0]
Çıktı: false
Açıklama: -4 ve 4 aynı mutlak değere sahiptir ancak farklı sayılardır ve 0 bir kez görünür, bu yüzden yanıt false olur.

Ek soru

Dizinin tamamını her zaman okumak yerine, ilk tekrarlanan değerle karşılaşır karşılaşmaz durabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Tekrar, daha önce karşılaştığınız bir değerdir ve işin özü, “bununla daha önce karşılaştım mı?” sorusunu hızlıca yanıtlamaktır. Her çifti karşılaştırmak bu soruyu yanıtlar, ancak n = 10^4 için bu, yaklaşık 5 × 10^7 karşılaştırma demektir: n(n-1)/2. Sıralama, eşit değerleri yan yana getirir ve bir hash kümesi soruyu ortalama olarak O(1) zamanda yanıtlar; böylece tek bir geçiş yeterli olur.

Sırala, ardından komşuları karşılaştır

Sezgi

Sıralanmış bir dizide eşit değerler yan yana gelir. [3, 1, 4, 1, 5], [1, 1, 3, 4, 5] şeklinde sıralanır ve iki 1 artık yan yanadır. Bu yüzden sıralamadan sonra her değeri yalnızca hemen önündeki değerle karşılaştırırsın: her çifti denemek için gereken n(n-1)/2 karşılaştırma yerine n-1 karşılaştırma.

Hiçbir komşu eşit değilse, hiçbir yerdeki iki değer de eşit değildir: sıralı düzende x'in iki kopyası arasında yer alan herhangi bir değer hem en az x hem de en fazla x olmak zorundadır; dolayısıyla o da başka bir x olur.

Sıralama işlemi O(n log n) zaman karmaşıklığına hâkimdir. nums dizisini yerinde sıralamak ek bir dizi gerektirmez, ancak çağıranın girdisinin sırasını değiştirir; buna izin verilmiyorsa O(n) alan maliyeti olan bir kopyayı sırala.

Algoritma

nums dizisini artan sırada sırala.
i değerini 1'den son indekse kadar döngüye sok.
nums[i], nums[i-1] değerine eşitse true döndür.
Döngüden sonra false döndür.

def containsDuplicate(nums):
    nums.sort()
    # After sorting, equal values sit next to each other.
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Bir hash kümesiyle tek geçiş

Sezgi

Diziyi bir kez dolaşın ve üzerinden geçtiğiniz her değeri bir karma kümesinde tutun. Bir değer eklemeden önce, kümede zaten olup olmadığını kontrol edin. [3, 1, 4, 1, 5] için küme {3, 1, 4} hâline gelir ve ikinci 1 geldiğinde küme bu değeri zaten içerir; bu yüzden 5 değerini okumadan true döndürürsünüz.

Küme her zaman geçerli konumdan önceki değerleri tam olarak içerir; dolayısıyla eşleşme, geçerli değerin daha önce göründüğü anlamına gelir. Eşleşme olmadan sona ulaşmak ise tüm değerlerin birbirinden farklı olduğu anlamına gelir.

Karma kümesinde arama ve ekleme, ortalama olarak O(1) zaman alır; bu nedenle tüm geçiş O(n) sürer. Bunun bedeli bellektir: tekrar yoksa küme, sonunda n değerin tümünü içerir.

Algoritma

Boş bir hash kümesi seen oluştur.
nums içindeki her değer için, değer seen içindeyse true döndür.
Aksi takdirde onu seen kümesine ekle.
Döngüden sonra false döndür.

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Tuzaklar ve uç durumlar

Mantık kısa, bu yüzden hatalar döngü sınırlarında ve neyi karşılaştırdığınızda gizlidir.

İç döngüyü j = i noktasından başlatarak her çifti karşılaştırmak. Böylece her değer kendisiyle eşleşir ve yanıt her zaman true olur.
Önce sıralamadan komşuları karşılaştırmak. [9, 1, 2, 3, 9] dizisindeki iki 9 yan yana değildir.
Komşu döngüsünü 0 indeksinden başlatıp nums[-1] değerini okumak. 1’den başlayın; tek değerli bir dizi doğru şekilde false döndürür.
Mutlak değerleri aynı olan değerleri eşit kabul etmek; örneğin abs(x) değerinin özetini almak. -4 ve 4 farklı sayılardır.
x - y döndüren bir C sıralama karşılaştırıcısı yazmak. Burada fark ±2 × 10^9 sınırları içinde kalır; bu da int sınırı olan 2^31-1 = 2147483647 değerinin altındadır, dolayısıyla bu durumda sığar. Ancak int sınırlarına yakın değerlerde taşmaya neden olur ve sıralama yanlış sonuç verir. Bunun yerine (x > y) - (x < y) döndürün.

Sıkça sorulan sorular3

Contains Duplicate'ın zaman karmaşıklığı nedir?

Küme (hash set) çözümü ortalama olarak O(n) zamanda çalışır ve O(n) ek alan kullanır. Önce sıralamak O(n log n) zaman alır ve girdiyi yeniden sıralayabiliyorsanız ek dizi gerektirmez. Her çifti karşılaştırmak O(n²) zaman alır.

Ekstra alan kullanmadan Contains Duplicate problemini çözebilir misin?

Evet, diziyi yeniden sıralamanıza izin veriliyorsa: diziyi yerinde sıralayın ve her değeri komşusuyla karşılaştırın. Böylece O(n) küme yerine O(n log n) zaman kullanılır. Yeniden sıralama yapmadan ve ek bellek kullanmadan geriye kalan tek seçenek O(n²) ikili kontroldür.

Bir hash kümesi kontrolü neden hızlı yapar?

Bir karma kümesi değerleri karmalarına göre saklar; bu nedenle bir değeri içerip içermediğini sormak, tarama yapmak yerine ortalama olarak sabit zaman alır. Her öğe için bir arama ve bir ekleme işlemi gerekir; bu da tüm geçişi doğrusal zamanlı hâle getirir.

def containsDuplicate(nums):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

nums = [3, 1, 4, 1, 5]

Beklenen Çıktı

true