Sort Colors
Her değeri 0, 1 veya 2 olan bir nums dizisi veriliyor. Bunları örneğin kırmızı, beyaz ve mavi olmak üzere üç renk olarak düşünün. Diziyi, önce tüm 0'lar, sonra tüm 1'ler, ardından tüm 2'ler gelecek şekilde yeniden düzenleyin ve diziyi döndürün.
Bunu bir kütüphane sıralama işlevi kullanmadan çözün. Amaç, değerler hakkında bildiklerinizi kullanmaktır.
Fonksiyon
- numsinteger-array
- renkler, her biri 0, 1 veya 2
- Döndürürinteger-array
- önce tüm 0'lar, ardından tüm 1'ler ve sonra tüm 2'lerle aynı değerler
Kısıtlar
1 ≤ nums.length ≤ 1.5 × 104- Her
nums[i]değeri0,1veya2'dir. - Bir renk eksik olabilir ve dizi tek bir renk içerebilir.
Örnekler
- Girdi
- nums = [2, 1, 0, 2, 0, 1, 1]
- Çıktı
- [0, 0, 1, 1, 1, 2, 2]
- Açıklama
- Dizi iki tane 0, üç tane 1 ve iki tane 2 içerir; dolayısıyla sonuç tam olarak şöyledir: önce iki tane 0, sonra üç tane 1, ardından iki tane 2.
- Girdi
- nums = [2, 0, 2]
- Çıktı
- [0, 2, 2]
- Açıklama
- Hiç 1 yok. Tek 0 başa geçer ve iki 2 onu takip eder.
- Girdi
- nums = [1]
- Çıktı
- [1]
- Açıklama
- Tek bir değer zaten sıralıdır, bu nedenle dizi değişmeden geri döner.
Gönderirken +17 gizli test
Ek soru
Dizinin uzunluğundan çok daha küçük olan üç renk yerine k renk olsaydı neyi değiştirirdin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Yalnızca üç farklı değer görünebilir. Bu, genel bir sıralamanın yapamayacağı neyi yapmanı sağlar?
0'ları, 1'leri ve 2'leri sayıp diziyi yeniden yazmak iki geçişte yapılır. Bir geçiş için aynı anda büyüyen üç bölge hayal et: önde 0'lar, arkada 2'ler, arada 1'ler.
Üç indeks tutun:
low,midvehigh.nums[mid]değerini okuyun: 0,lowile yer değiştirir; 2,highile yer değiştirir; 1 olduğu yerde kalır.highile yer değiştirdikten sonra aynı konumu tekrar okuyun.
Çözüm
Herhangi bir sıralama doğru sırayı verir; dolayısıyla asıl soru, üç değerin hangi adımları atlamanı sağladığıdır. Yalnızca 0, 1 ve 2 görünebildiğinden, bunları sayıp diziyi iki geçişte yeniden yazabilirsin. 0'ların nerede bittiğini ve 2'lerin nerede başladığını belirleyen üç işaretçiyle, her değeri tek bir geçişte doğru yerine bile koyabilirsin. Bu tek geçişli bölümleme, Hollanda ulusal bayrağı algoritmasıdır.
Elle kabarcık sıralaması
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Bir kütüphane sıralaması O(n log n) sürede çalışırdı, ancak problem bunu yasaklıyor; çünkü bir görüşmeci, yalnızca üç değer olduğu gerçeğini nasıl değerlendirdiğini görmek istiyor. Bu durumda temel yaklaşım, sıralamayı kendin yazmaktır ve doğru şekilde uygulaması en kolay olanı bubble sort'tur: dizi boyunca ilerle ve iki komşu sırası yanlışsa yerlerini değiştir.
Bir geçiş, karşılaştığı en büyük değeri bir balonun yükselmesi gibi sonuna kadar taşır. İlk geçişten sonra son konum kesinleşir, ikinci geçişten sonra sondan iki konum kesinleşir; böylece n-1 geçiş dizinin tamamını sıralı hâle getirir. [2, 1, 0] dizisinde ilk geçiş 2'yi sona taşır ve [1, 0, 2] elde edilir; ikinci geçişte ise 1 ile 0'ın yerleri değiştirilir.
Yavaştır, çünkü her geçişte henüz son konumuna yerleşmemiş her çift karşılaştırılır: toplamda yaklaşık n²/2 karşılaştırma. n = 1.5 × 10^4 olduğunda bu, 10^8'den fazla karşılaştırma demektir; buna, başlangıçta sırası yanlış olan her çift için bir yer değiştirme de eklenir ve yapılan bu işlerin hiçbiri yalnızca üç değer olduğu gerçeğinden yararlanmaz.
Algoritma
- Dizi üzerinde n-1 geçiş yapın.
- Her geçişte, henüz son konumunda olmayan
nums[j]venums[j + 1]komşu çiftlerini karşılaştırın ve soldaki daha büyük olduğunda yerlerini değiştirin. - 0'dan başlayarak sayılan
donenumaralı geçişten sonra, sondakidone + 1konum son değerlerini alır; bu nedenle sonraki geçiş bu konumlardan önce durur. numsdeğerini döndürün.
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return numsHer rengi say, sonra yeniden yaz
Sezgi
Kabarcık sıralaması tüm zamanını komşuları karşılaştırarak geçirir, ancak hangi değerlerin bulunduğunu zaten biliyorsun. Dizi iki tane 0, üç tane 1 ve iki tane 2 içeriyorsa, hiçbir şeyi hareket ettirmeden önce cevap bellidir: iki tane 0, üç tane 1, iki tane 2. Önemli olan yalnızca sayılardır.
Bu yüzden diziyi bir kez oku ve her değeri say. Ardından dizinin üzerine baştan başlayarak yaz: count[0] tane sıfır, sonra count[1] tane bir, sonra count[2] tane iki. Bu, sayma sıralamasıdır ve burada güvenlidir; çünkü eşit değerler birbirinin yerine kullanılabilir. 1 yine 1'dir, dolayısıyla özgün sıranın korunması gerekmez.
Bu, iki geçiş ve üç sayaç demektir; zaman karmaşıklığı O(n), alan karmaşıklığı O(1)'dir. Sınırları karşılar ve çok sayıda renk olduğunda doğal çözümdür. Bu problemle anılan devam sorusu, bunu diziyi yalnızca bir kez okuyarak yapıp yapamayacağındır.
Algoritma
- Üç sayaç oluşturun, hepsi 0 olsun.
- Her değeri okuyun ve ilgili sayacı bir artırın.
- Baştan başlayarak
count[0]tane sıfır, ardındancount[1]tane bir, sonracount[2]tane iki yazın. numsdeğerini döndürün.
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return numsÜç işaretçiyle tek geçiş (Hollanda bayrağı)
Sezgi
Okurken üç bölgeyi büyütün: başta 0’lar, onların ardından 1’ler, sonda 2’ler ve 1’lerle 2’lerin arasında okunmamış bir bölüm. Sınırları üç indeks işaretler. low öncesindeki her şey 0, low konumundan başlayıp mid konumuna kadar (bu konum hariç) olan her şey 1, high sonrasındaki her şey 2’dir; nums[mid] ile nums[high] arasındaki bölüm ise hâlâ okunmamıştır.
nums[mid] değerini okuyun. 1 zaten kendi bölgesindedir, bu yüzden mid değerini ilerletin. 0 başta olmalıdır: onu nums[low] ile takas edin ve hem low hem de mid değerlerini ilerletin. low konumundan gelen değer 1’dir (ya da henüz hiç 1 görülmediyse aynı 0’dır), dolayısıyla zaten yerindedir. 2 sonda olmalıdır: onu nums[high] ile takas edin ve high değerini geriye alın, ancak mid değerini bulunduğu yerde tutun; çünkü high konumundan gelen değer henüz okunmamıştır.
Her adımda mid ilerler veya high geriler; böylece okunmamış bölüm her seferinde bir hücre küçülür ve döngü n adımdan sonra sona erer. [2, 0, 2] dizisini izleyin: ilk 2 son 2 ile takas edilir ve high 1’e düşer; 0. indeks hâlâ 2 içerir, bu değer 0 ile takas edilir ve high 0’a düşer; 0. indeks şimdi 0 içerir, bu değer yerinde kalır ve [0, 2, 2] elde edilir.
Algoritma
low = 0,mid = 0olarak ayarla vehighdeğerini son indekse ayarla.mid ≤ higholduğu sürecenums[mid]değerini oku.- Değer 0 ise,
nums[low]ile yer değiştir velowilemiddeğerlerini bir adım sağa ilerlet. - Değer 1 ise,
middeğerini bir adım sağa ilerlet. - Değer 2 ise,
nums[high]ile yer değiştir vehighdeğerini bir adım sola ilerlet.middeğerini olduğu yerde bırak. numsdeğerini döndür.
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
Tuzaklar ve uç durumlar
Tek geçişli sürüm kısadır ve içindeki hataların neredeyse tamamı, hareket etmemesi gereken bir işaretçinin hareket etmesinden kaynaklanır.
highile takas ettikten sonramidişaretçisini ilerletmek. Gelen değer henüz okunmamıştır.[1, 2, 0]üzerinde 2, 0 ile yer değiştirir ve 0 atlandığında[1, 0, 2]döndürülür.highson okunmamış indekskenmid < highkoşuluyla döngü kurmak. İkisi buluştuğunda o hücre hâlâ okunmamıştır.[1, 0]üzerinde döngü, 0'ı okumadan durur ve[1, 0]döndürür.- İşaretsiz bir indeks kullanırken
highdeğerinin sıfırın altına düşmesine izin vermek. Yalnızca 2'lerden oluşan[2]gibi bir dizi,highdeğerini -1'e getirir. İndekslerinusizeolduğu Rust'ta, Rust kodunun yaptığı gibihighdeğerini bunun yerine okunmamış kısmın bir ötesinde tut. - Her rengin dizide bulunduğunu varsaymak.
[2, 0, 2]içinde 1 yoktur ve bir dizi tek bir renk içerebilir. İşaretçi kuralları her iki durumu da özel durumlara gerek kalmadan ele alır; bu yüzden böyle durumlar ekleme.
Sıkça sorulan sorular4
Hollanda bayrağı problemi nedir?
Edsger Dijkstra bunu şöyle ortaya koydu: Bir sıra hâlinde üç renkten nesneler verildiğinde, Hollanda bayrağının kırmızı, beyaz ve mavisini, yalnızca yer değiştirme işlemlerini kullanarak tek geçişte renklerine göre gruplayın. Sort Colors, 0, 1 ve 2 sayılarıyla aynı problemdir. Çözümü, low, mid ve high ile yapılan üç işaretçili bölümlendirmedir.
Sort Colors'ın zaman ve uzay karmaşıklığı nedir?
Tek geçişli çözüm O(n) zamanda çalışır, çünkü her adım okunmamış kısmı bir hücre küçültür. O(1) ek alan kullanır: üç indeks ve yer değiştirme için geçici bir değer. Sayma sıralaması da aynı sınırlara sahiptir, ancak diziyi iki kez okur.
mid, high ile yer değiştirdikten sonra neden hareket etmiyor?
high değerinden geri gelen değer hiç okunmadı, bu yüzden 0, 1 veya 2 olabilir. mid değerini onun ötesine taşımak, ortada 0 veya 2 bırakır. low ile yapılan bir takas farklıdır: low ile mid arasındaki her şey 1 olduğundan, geri gelen değer bilinir ve mid ilerleyebilir.
Renkleri Sırala için sayma sıralaması kabul edilebilir bir yanıt mıdır?
O(n) zaman ve O(1) alan sınırlarını karşılar ve birçok mülakatçı bunu ilk yanıt olarak kabul eder. Tek geçiş isteyen devam sorusunu bekleyin; bu, üç işaretçili bölümlemedir. Çok sayıda renk olduğunda sayma daha iyi bir yöntemdir, çünkü bölümleme yalnızca üç gruba ayırır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def sortColors(nums):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums = [2, 1, 0, 2, 0, 1, 1]
Beklenen
[0, 0, 1, 1, 1, 2, 2]