Longest Consecutive Sequence
Belirli bir sırada olmayan bir tamsayı dizisi nums alırsın. Ardışık bir dizi, nums içinde bir yerde bulunan x, x+1, x+2 ve benzeri değerlerden oluşan bir gruptur. En uzun ardışık dizinin uzunluğunu döndür. Birden fazla kez görünen bir değer bir kez sayılır.
Fonksiyon
- numsinteger-array
- tamsayılar, herhangi bir sırada; tekrarlar serbesttir
- Döndürürinteger
- nums içinde bulunan ardışık değerlerin en uzun dizisinin uzunluğu
Kısıtlar
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- Değerler tekrarlanabilir. Dizideki konumlar önemli değildir; yalnızca hangi değerlerin bulunduğu önemlidir.
Örnekler
- Girdi
- nums = [40, 4, 39, 1, 3, 2, 41]
- Çıktı
- 4
- Açıklama
1,2,3ve4dizinin farklı yerlerine dağılmış olsalar da hepsi mevcut; yani 4 elemanlık bir ardışık dizi oluşturuyorlar. Diğer ardışık dizi olan39ile41arasında yalnızca 3 değer var.
- Girdi
- nums = [7, 3, 7, 5, 6, 5]
- Çıktı
- 3
- Açıklama
5,6ve73 uzunluğunda bir ardışık dizi oluşturur. İkinci7ve ikinci5hiçbir şey katmaz,4eksik olduğundan3katılamaz.
- Girdi
- nums = [10, 30, 20]
- Çıktı
- 1
- Açıklama
- Hiçbir iki değer arasında 1 fark yoktur, bu nedenle her dizi tek bir değer içerir ve sonuç 1'dir.
Gönderirken +17 gizli test
Ek soru
Diyelim ki değerler teker teker geliyor ve her birinden sonra şu ana kadarki en uzun ardışık diziyi bildirmeniz gerekiyor. Her değer başına ortalama O(1) zamanda yanıtı güncel tutabilir misiniz?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir dizinin ilk sayısı olarak her değeri dene ve sayarak ilerle. Hangi soruyu tekrar tekrar soruyorsun ve dizide ararken her yanıtın maliyeti nedir?
Soru, "
x+1dizide mi?" şeklindedir. Bir hash kümesi bu soruyu ortalama sabit zamanda yanıtlar ve yinelenenleri de kaldırır.Yalnızca
xdeğerini,x-1kümede yoksa saymaya başlayın. Buradanx+1,x+2değerlerine ve kümede bulundukları sürece devam edin; en uzun yürüyüşü saklayın. Böylece her değerin üzerinden yalnızca bir yürüyüş geçer.
Çözüm
Bir serinin değerleri dizinin herhangi bir yerinde bulunabilir; bu nedenle serileri soldan sağa okuyamazsın. Sıralama, bunları O(n log n) süresinde bir araya getirir. Bir hash kümesi daha iyisini yapar: x+1 burada mı? sorusunu O(1) süresinde yanıtlar ve yalnızca x-1 değeri eksik olan değerlerden saymaya başlarsan, her değerin üzerinden bir kez geçilir; böylece aramanın tamamı O(n) olur.
Dizide arama yaparak her değerden başlayıp say
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her değeri bir dizinin başlangıcı olabilecekmiş gibi ele al. x değerinden başlayarak dizide x+1 değerini ara; oradaysa x+2 değerini ara ve bir değer eksik olana kadar devam et. Ulaştığın değerlerin sayısı, x değerinde başlayan dizinin uzunluğudur; bu uzunlukların en büyüğü de yanıttır.
Bu doğrudur çünkü her dizinin en küçük bir değeri vardır, bu değer nums içindedir ve döngü bunu başlangıç olarak deneyip dizinin tamamı boyunca ilerler. Tekrarların zararı olmaz: yalnızca aynı başlangıcı iki kez denerler.
İki açıdan yavaştır. Her “burada mı?” araması n değere kadar okur ve uzun bir dizinin her üyesinden yeniden geçilir. Karıştırılmış tek bir dizi oluşturan 10^4 değer alalım: geçişlerin toplamı yaklaşık n²/2 = 5 × 10^7 adım eder ve her adım diziyi ortalama yarısına kadar tarar. Bu da yaklaşık 2.5 × 10^11 karşılaştırma demektir.
Algoritma
bestdeğerini 0 olarak ayarla.numsiçindeki herstartdeğeri içincurrentdeğerinistart,lengthdeğerini ise 1 olarak ayarla.numstaramasındacurrent+1bulunduğu sürececurrentvelengthdeğerlerini 1 artır.- Daha büyükse
lengthdeğerinibestiçine kaydet. bestdeğerini döndür.
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return bestSırala, ardından ardışık grupları say
Sezgi
Sıralama, her dizideki değerleri yan yana getirir. [40, 4, 39, 1, 3, 2, 41] şu hale gelir: [1, 2, 3, 4, 39, 40, 41] ve diziler soldan sağa okunur: 1'den 4'e kadar, ardından 39'a sıçrama.
Sıralanmış değerler üzerinde ilerleyin ve geçerli dizinin uzunluğunu takip edin. Öncekinden bir fazla olan bir değer diziyi uzatır. Önceki değere eşit olan bir değer tekrardır: atlayın, çünkü ne diziyi uzatır ne de bitirir. Diğer herhangi bir değer bir boşluktur ve orada uzunluğu 1 olan yeni bir dizi başlar.
Sıralama O(n log n), ilerleme ise O(n) maliyetindedir. Yerinde sıralama ek bir dizi gerektirmez ancak çağıranın girdisini yeniden sıralar; kopyayı sıralayan diller O(n) bellek kullanır.
Algoritma
numsdizisini artan sırada sırala.- Dizi hiçbir zaman boş olmadığından
bestverundeğerlerini 1 olarak ayarla. - 1'den başlayarak her
iindeksi için,nums[i]değerinums[i-1]değerine eşitse atla. nums[i]değerinums[i-1]+1iserundeğerine 1 ekle; aksi hâlderundeğerini 1 olarak ayarla. Daha büyükserundeğerinibestiçine kaydet.bestdeğerini döndür.
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return bestHash kümesi, yalnızca her çalıştırmanın başlangıcından itibaren sayar
Sezgi
Her değeri bir hash kümesine koy. Böylece “x+1 mevcut mu?” kontrolü, tarama yapmak yerine ortalama O(1) maliyetlidir ve tekrarlar tek bir girdide birleşir.
Her değerden başlamak yine işleri tekrarlar: 1, 2, 3, 4 dizisinde 1'den 3 adım, 2'den 2 adım ve 3'ten 1 adım atarsın. Bu yüzden bir yürüyüşe yalnızca bir dizinin ilk değerinden başla. x değeri, tam olarak x-1 kümede değilse ilk değerdir. [40, 4, 39, 1, 3, 2, 41] içinde yalnızca 1 ve 39 koşulu sağlar: 1'den 4'e ulaşırsın; uzunluk 4 olur. 39'dan ise 41'e ulaşırsın; uzunluk 3 olur.
Her değer tam olarak bir diziye aittir ve yalnızca o dizinin ilk değerinden başlayan yürüyüş üzerinden geçer; bu nedenle tüm yürüyüşler birlikte en fazla n adım atar. Her değer için bir üyelik kontrolü ve kümenin oluşturulmasını eklediğinde toplam süre O(n), küme için gereken bellek ise O(n) olur.
nums üzerinde değil, küme üzerinde döngü kur. 2.500 değerlik bir dizinin ilk değeri nums içinde 2.000 kez geçiyorsa, nums üzerinde döngü kurmak o dizide 2.000 kez yürür.
Algoritma
numsiçindeki her değeri bir karma kümesi olanvaluesiçine koy vebestdeğerini 0 olarak ayarla.- Kümedeki her
xdeğeri için,x-1kümedeyse atla: bu, dizisinin ilk değeri değildir. - Aksi hâlde
enddeğerinixolarak ayarla veend+1kümede olduğu sürece ona 1 ekle. - Daha büyükse
end-x+1değerinibestiçinde sakla. bestdeğerini döndür.
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
Tuzaklar ve uç durumlar
Yanlış yanıtların çoğu yinelenen değerlerden, yavaş yanıtların çoğu ise aynı diziyi birden fazla kez dolaşmaktan kaynaklanır.
- Yinelenen bir değeri boşluk ya da sıralama sonrasında bir adım olarak ele almak.
[1, 2, 2, 3]içinde, ikinci2değerinde diziyi sıfırlamak 2 verir; onu bir adım olarak saymak ise 4 verir. Doğru yanıt 3’tür. - Sıralı taramada
bestdeğerini 0’dan başlatıp yalnızca döngünün içinde güncellemek. Bu durumda tek değerli bir dizi, 1 yerine 0 döndürür. - Yalnızca dizi başlangıçlarından başlamak yerine kümedeki her değerden başlayarak dolaşmak. Yanıt doğrudur, ancak
10^4değerlik tek bir dizi5 × 10^7adıma mal olur; kümenin ortadan kaldırması amaçlanan karesel iş yükü budur. - Değerler yinelendiğinde küme yerine
numsüzerinde döngü kurmak. Binlerce kez görünen bir değerden başlayan dizi, binlerce kez dolaşılır. - Değer indeksli bir dizide değerleri işaretlemek. Değerler
±10^9düzeyine ulaşır; dolayısıyla dizinin2 × 10^9girişe ihtiyacı olur.
Sıkça sorulan sorular4
En Uzun Ardışık Dizi'nin zaman karmaşıklığı nedir?
Karma küme çözümü ortalama olarak O(n) zamanda çalışır ve O(n) ek bellek kullanır. Sıralama ve ardından dizileri sayma işlemi O(n log n) zaman alır. Küme kullanmadan her sonraki değeri dizide aramak, O(n³) kadar zaman alabilir.
İç içe bir for döngüsü içinde while döngüsü bulunmasına rağmen hash kümesi çözümü neden O(n)?
İç döngü yalnızca sol komşusu x-1 bulunmayan bir değerden, yani dizisinin ilk değerinden başlayarak çalışır. Her değerin üzerinden yalnızca kendi dizisinin yürüyüşü geçer; başka hiçbir yürüyüş geçmez. Bu nedenle tüm iç döngüler birlikte en fazla n adım sürer. Dış döngü, her değer için bir kontrol ekler; toplamda O(n) olur.
En Uzun Ardışık Dizi problemini ek bellek kullanmadan çözebilir misin?
Evet, girdiyi yeniden sıralayabiliyorsan: yerinde sırala ve tekrarları atlayarak tek geçişte dizileri say. Bu, ek bellek olarak O(1) kullanır, ancak O(n log n) zaman alır. O(n) çözümü hash kümesi gerektirir.
Birleşim-bulma, En Uzun Ardışık Dizi problemini çözebilir mi?
Evet. Her farklı değeri bir kümeye dönüştürün, ikisi de mevcut olduğunda x ile x+1 değerlerini birleştirin ve en büyük kümenin boyutunu döndürün. Yaklaşık O(n) zamanda çalışır, ancak değer-indeks eşlemesi, ebeveyn bağlantıları ve boyutlar gerektirir; hash kümesi üzerinde dolaşmak ise aynı işi bir küme ve iki döngüyle yapar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def longestConsecutive(nums):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums = [40, 4, 39, 1, 3, 2, 41]
Beklenen
4