Longest Consecutive Sequence
Sana belirli bir sıralaması olmayan bir tamsayı dizisi nums verilir. Ardışık bir dizi, her biri 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
- tam sayılar, herhangi bir sırada, tekrara izin verilir
- Döndürürinteger
- nums'ta bulunan ardışık değerlerin en uzun serisinin 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 içinde dağınık olsalar da hepsi mevcut; yani 4'lük bir dizi oluşturuyorlar. Diğer dizi olan39ile41arasında ise yalnızca 3 değer var.
- Girdi
- nums = [7, 3, 7, 5, 6, 5]
- Çıktı
- 3
- Açıklama
5,6ve73'lük bir ardışık dizi oluşturur. İkinci7ve ikinci5hiçbir katkı sağlamaz ve4eksik olduğu için3diziye katı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 yanıt 1'dir.
Ek soru
Değerlerin teker teker geldiğini ve her birinden sonra o ana kadarki en uzun ardışık diziyi bildirmen gerektiğini varsayalım. Her değer için ortalama O(1) zamanda yanıtı güncel tutabilir misin?
İ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 saymaya devam et. Tekrar tekrar hangi soruyu 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 tekrarları da kaldırır.Yalnızca
xdeğerinden saymaya başlayın; bu değerinx-1değeri kümede bulunmamalıdır. Buradanx+1,x+2değerlerine ve kümede bulundukları sürece sonraki değerlere ilerleyin ve en uzun diziyi koruyun. Böylece her değerin üzerinden yalnızca bir dizi geçer.
Çözüm
Bir dizideki ardışık değerler herhangi bir yerde bulunabilir. Sıralama onları O(n log n) süresinde yan yana getirir. Bir hash kümesi, "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: toplamda O(n).
Dizide arama yaparak her değerden itibaren sayın
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her değeri bir dizinin olası başlangıcı olarak ele al. x değerinden başlayarak dizide x+1 değerini, ardından x+2 değerini ara; bir değer bulunmayana kadar devam et ve en uzun sayıyı tut. Her dizinin nums içinde en küçük bir değeri vardır ve döngü dizinin tamamını bu değerden başlayarak tarar.
Her arama en fazla n değeri okur ve uzun bir dizi, her elemanından tekrar taranır. Tek bir karışık diziyi oluşturan 10^4 değer için taramalar yaklaşık n²/2 = 5 × 10^7 adım sürer; her biri ortalama olarak dizinin yarısını tarar: yaklaşık 2.5 × 10^11 karşılaştırma.
Algoritma
bestdeğerini 0 olarak ayarla.numsiçindeki herstartdeğeri içincurrentdeğerinistartolarak,lengthdeğerini ise 1 olarak ayarla.numstaramasındacurrent+1bulunduğu sürececurrentvelengthdeğerlerini 1 artır.- Daha büyükse
lengthdeğerinibestiçinde sakla. 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 tekrarları say
Sezgi
Sıralama, her ardışık dizideki değerleri yan yana getirir: [40, 4, 39, 1, 3, 2, 41] şu hâle gelir: [1, 2, 3, 4, 39, 40, 41]; ardışık diziler soldan sağa okunur.
Sıralanmış değerler üzerinde ilerleyin ve geçerli ardışık dizinin uzunluğunu takip edin. Öncekinden bir fazla olan değer diziyi uzatır. Tekrarlanan bir değer diziyi ne uzatır ne de bitirir; bu yüzden onu atlayın. Diğer her değer, uzunluğu 1 olan yeni bir dizi başlatır.
Sıralama işleminin maliyeti O(n log n), üzerinden geçme işleminin maliyeti O(n) olur. Yerinde sıralama ek dizi gerektirmez; 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şlayan her
iindeksi için,nums[i]değerinums[i-1]değerine eşitse bu öğeyi atla. nums[i]değerinums[i-1]+1iserundeğerine 1 ekle; değilserundeğ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 bestHer çalıştırmanın yalnızca başlangıcından itibaren sayan hash kümesi
Sezgi
Hash kümesindeki her değer için üyelik denetimi ortalama O(1) maliyetlidir ve tekrarlar tek bir girdide birleştirilir.
Her değerden yürümek yine de aynı işlemi tekrar ederdi: 1, 2, 3, 4 dizisinde 1'den 3 adım, 2'den 2 adım ve 3'ten 1 adım atardınız. Bu yüzden yalnızca bir dizinin ilk değerinden yürüyün; bu, x-1 değeri eksik olan x değeridir. Örnek 1'de yalnızca 1 ve 39 bu koşulu sağlar; böylece uzunlukları 4 ve 3 olan diziler elde edilir.
Her değer bir diziye aittir ve yalnızca o dizinin yürüyüşü sırasında üzerinden geçilir; dolayısıyla tüm yürüyüşler toplamda en fazla n adım sürer. Değer başına bir denetimle toplam süre O(n), küme için gereken bellek ise O(n) olur.
Algoritma
numsiçindeki her değerivaluesadlı bir hash kümesine koy vebestdeğerini 0 olarak ayarla.- Kümedeki her
xdeğeri için, kümedex-1varsa atla: bu, dizisinin ilk değeri değildir. - Aksi takdirde
enddeğerinixolarak ayarla ve kümedeend+1olduğu süreceenddeğerini 1 artır. - 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
- Tekrarı, sıralama sonrasında boşluk veya adım olarak değerlendirmek.
[1, 2, 2, 3]içinde ikinci2değerinde diziyi sıfırlamak 2 sonucunu verir; bunu bir adım olarak saymak ise 4 sonucunu verir. Doğru cevap 3'tür. - Sıralı geçişte
bestdeğerini 0 olarak başlatmak ve yalnızca döngünün içinde güncellemek. Böylece tek değerli bir dizi 1 yerine 0 döndürür. - Yalnızca dizi başlangıçlarından değil, kümedeki her değerden başlayarak ilerlemek.
10^4değerlik tek bir dizi,5 × 10^7adım gerektirir. - Küme yerine
numsüzerinde döngü kurmak. 2.500 değerlik bir dizinin ilk değeri 2.000 kez görünüyorsa dizi 2.000 kez taranır. - Diziyi değere göre indekslemek. Değerler
±10^9değerine ulaşır; bu nedenle2 × 10^9giriş gerekir.
Sıkça sorulan sorular3
En Uzun Ardışık Dizi'nin zaman karmaşıklığı nedir?
Küme karması çözümü ortalama olarak O(n) zamanda çalışır ve O(n) ek bellek kullanır. Sıralama ve ardışık değerleri sayma işlemleri O(n log n) zaman alır. Küme kullanmadan her sonraki değeri dizide aramak O(n³) kadar zaman alabilir.
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 grupları say. Bu, ek bellek olarak O(1) kullanır ancak O(n log n) zaman alır. O(n) çözümü için hash kümesi gerekir.
Birleş-Bul yapısı En Uzun Ardışık Diziyi çözebilir mi?
Evet. Her farklı değeri bir küme yapı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. O(n) zamanına yakın sürede çalışır, ancak hash kümesi dolaşımı tek bir küme gerektirirken değer-indeks eşlemesi, üst bağlantıları ve boyutlar gerektirir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def longestConsecutive(nums):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
nums = [40, 4, 39, 1, 3, 2, 41]
Beklenen Çıktı
4