LeetCode 128 · Longest Consecutive Sequence · Medium

En Uzun Ardışık Dizi

Çözümün her adımını burada izleyebilirsin. Bir dizi seç, İleri'ye bas ya da Oynat'a tıkla; sadece grup başlarından saymanın, aynı grubu tekrar tekrar saymayı nasıl önlediğini gör.

Fikir üç adımda

  1. 1

    Sayıları bir sete koy

    HashSet, "bu sayı var mı?" sorusunu diziyi taramadan, anında cevaplar. Tekrar eden sayılar sete bir kez girer.

  2. 2

    Sadece grup başlarından say

    Bir sayının bir eksiği sette yoksa o sayı bir grubun başıdır. Başı olmayan sayıları atlıyoruz; böylece her grup bir kez sayılıyor.

  3. 3

    Baştan ileri doğru say

    Grup başından itibaren bir fazlası, onun bir fazlası… sette olduğu sürece uzunluğu artır. En uzun grubu longest'ta tut.

Adım adım izle

nums (tekrar edenler sete girmez)
foreach sırası (set, sayıların eklendiği sırayla)

Set, sayı doğrusunda (küçükten büyüğe; "…" arada eksik sayı olduğunu gösterir)

num (bakılan sayı) sette var mı diye bakılan sayı sette yok şu an sayılan grup şimdiye kadarki en uzun grup

Değişkenler

Kod (Solution.cs içindeki metot)

Neden O(n)?

Kodda bir foreach ve içinde bir while var; ilk bakışta O(n²) gibi görünüyor. Ama while sadece grup başlarında çalışıyor ve her sayı en fazla bir grubun içinde sayılıyor. Toplamda her sayıya foreach'te bir kez, while'da en fazla bir kez bakılıyor: O(n) zaman. Set n sayı tuttuğu için O(n) bellek kullanıyor.

Grup başı kontrolü olmasaydı her sayıdan ileri doğru sayardık. 0'dan 99.999'a kadar bütün sayıların olduğu bir dizide 0'dan 100.000, 1'den 99.999 adım… toplam yaklaşık 5 milyar adım ederdi.

foreach'in nums yerine set üzerinde dönmesi de önemli. Bir grubun başı dizide çok kez tekrar ediyorsa (örneğin 50.000 tane 1), nums üzerinde dönmek aynı grubu 50.000 kez sayar. Set'te her sayı bir kez olduğu için bu sorun olmuyor.

Diziyi sıralayıp baştan sona yürümek de doğru sonuç verir ve kodu daha kısadır. Ama sıralama O(n log n) sürer ve metoda verilen diziyi değiştirir. Set'li çözüm daha hızlı ve girdiye dokunmuyor.