Sort Colors

Q: Hollanda ulusal bayrağı problemi nedir?

Edsger Dijkstra bu problemi şöyle ortaya koydu: Üç renkteki nesneleri, Hollanda bayrağının kırmızı, beyaz ve mavisini, her renk bir arada olacak şekilde tek geçişte ve yalnızca yer değiştirme işlemleri kullanarak sırala. Sort Colors, 0, 1 ve 2 ile aynı problemdir ve onun çözümü üç işaretçili bölümlemedir.

Q: Sort Colors algoritmasının zaman ve alan 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 takas için geçici bir değer. Sayma sıralaması da aynı sınır değerlerine sahiptir, ancak diziyi iki kez okur.

Q: Renkleri Sıralama için sayma sıralaması kabul edilebilir bir yanıt mı?

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. Ardından tek geçişte çözüm sunmanızın istenmesini bekleyin. Bölümleme yalnızca üç gruba ayırdığı için, çok sayıda renk olduğunda sayma daha iyi bir yöntemdir.

Ortaİki işaretçi Sıralama

+10

Her değeri 0, 1 veya 2 olan bir nums dizisi alırsın: kırmızı, beyaz ve mavi gibi üç renk. Diziyi, önce tüm 0'lar, ardından tüm 1'ler ve sonra tüm 2'ler gelecek şekilde yeniden düzenle ve diziyi döndür. Bunu bir kütüphane sıralama işlevi kullanmadan çöz.

Fonksiyon

sortColors(nums: integer-array) → integer-array

numsinteger-array: renkler, her biri 0, 1 veya 2
Döndürürinteger-array: önce tüm 0'lar, sonra tüm 1'ler ve ardından tüm 2'lerle aynı değerler

Kısıtlar

1 ≤ nums.length ≤ 1.5 × 10⁴
Her nums[i] değeri 0, 1 veya 2'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 adet 0, üç adet 1 ve iki adet 2 içerir; dolayısıyla sonuç tam olarak şöyledir: önce iki adet 0, sonra üç adet 1, ardından iki adet 2.

Ek soru

Üç renk yerine k renk olsaydı ve k dizinin uzunluğundan çok daha küçük olsaydı neyi değiştirirdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Yalnızca 0, 1 ve 2 görünebilir; bu yüzden onları sayıp diziyi iki geçişte yeniden yazabilirsiniz. 0'ların bittiği yeri ve 2'lerin başladığı yeri işaretleyen üç işaretçi, her değeri okurken yerli yerine koyarak bunu tek geçişte yapar. Bu bölümleme, Hollanda ulusal bayrağı algoritmasıdır.

Elle balon sıralaması

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Bir kütüphane sıralaması olmadan temel seçenek, kendin yazdığın bir sıralama algoritmasıdır. Kabarcık sıralama, diziyi baştan sona tarar ve sırası yanlış olan komşu öğeleri yer değiştirir. Her geçiş, karşılaştığı en büyük değeri sona taşır; böylece n-1 geçişten sonra her konum kesinleşir.

Yaklaşık n²/2 karşılaştırma yapar: n = 1.5 × 10^4 için 10^8'den fazla; bu karşılaştırmaların hiçbiri yalnızca üç değer bulunduğu bilgisinden yararlanmaz.

Algoritma

Dizi üzerinde n-1 geçiş yap.
Her geçişte, henüz sıralanmamış komşu çiftleri nums[j] ve nums[j + 1] karşılaştır ve soldaki daha büyük olduğunda yerlerini değiştir.
Numarası done olan geçişten sonra (0'dan başlayarak sayıldığında), sondaki done + 1 konum son değerlerini alır; bu nedenle sonraki geçiş bu konumlara gelmeden durur.
nums değerini döndür.

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 nums

Her rengi sayın, ardından yeniden yazın

Sezgi

Eşit değerler birbirinin yerine kullanılabilir, bu yüzden yalnızca adetleri önemlidir. İlk örnekte, iki 0, üç 1 ve iki 2, herhangi bir şeyi taşımadan önce cevabı belirler.

Her değeri saymak için diziyi bir kez oku, ardından baştan başlayarak üzerine yaz: count[0] sıfır, count[1] bir, count[2] iki. Bu, sayma sıralamasıdır. İki geçiş ve üç sayaç, O(n) zaman ve O(1) alan sağlar.

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ından count[1] tane bir, sonra da count[2] tane iki yazın.
nums değ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 ulusal bayrağı)

Sezgi

Okurken üç bölgeyi genişletin. low öncesindeki her şey 0, low konumundan başlayıp mid konumunu içermeyen aralıkta kalan her şey 1, high sonrasındaki her şey 2'dir ve nums[mid] ile nums[high] arasındaki bölüm okunmamıştır.

nums[mid] değerini okuyun. 1 zaten kendi bölgesindedir, bu yüzden mid değerini ilerletin. 0, nums[low] ile yer değiştirir ve ikisi de ilerler: low konumundan geri gelen değer 1'dir ya da henüz hiç 1 görülmediyse aynı 0'dır; dolayısıyla doğru yerdedir. 2, nums[high] ile yer değiştirir ve high geri gider; ancak mid aynı kalır, çünkü high konumundan gelen değer henüz okunmamıştır.

Her adımda mid ilerler veya high geri gider; bu nedenle döngü n adım sonra biter. [2, 0, 2] üzerinde ilk 2 son elemanla yer değiştirir ve high 1'e düşer; 0. indeks hâlâ 2 içerir ve bu değer 0 ile yer değiştirir; ardından 0 yerinde kalır ve sonuç [0, 2, 2] olur.

Algoritma

low = 0, mid = 0 olarak ayarla ve high değerini son indekse ayarla.
mid ≤ high olduğu sürece nums[mid] değerini oku.
0 ise bunu nums[low] ile değiştir ve low ile mid değerlerini bir adım sağa ilerlet.
1 ise mid değerini bir adım sağa ilerlet.
2 ise bunu nums[high] ile değiştir ve high değerini bir adım sola ilerlet. mid değerini olduğu yerde bırak.
nums değ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

high ile yapılan takastan sonra mid değerini ilerletmek. Gelen değer okunmamıştır: [1, 2, 0] üzerinde 2, 0 ile takas edilir ve 0'ı atlamak [1, 0, 2] sonucunu verir.
mid < high iken döngüye devam etmek. İkisi buluştuğunda o hücre hâlâ okunmamıştır: [1, 0] üzerinde döngü, 0'ı okumadan durur ve [1, 0] sonucunu verir.
İşaretsiz bir indeksle high değerinin sıfırın altına düşmesine izin vermek. Yalnızca 2'lerden oluşan bir dizi, örneğin [2], high değerini -1'e düşürür; bu da Rust'ta bir usize değerinin taşmasına neden olur. Bunun yerine high değerini okunmamış kısmın bir ötesinde tut.

Sıkça sorulan sorular3

Hollanda ulusal bayrağı problemi nedir?

Edsger Dijkstra bu problemi şöyle ortaya koydu: Üç renkteki nesneleri, Hollanda bayrağının kırmızı, beyaz ve mavisini, her renk bir arada olacak şekilde tek geçişte ve yalnızca yer değiştirme işlemleri kullanarak sırala. Sort Colors, 0, 1 ve 2 ile aynı problemdir ve onun çözümü üç işaretçili bölümlemedir.

Sort Colors algoritmasının zaman ve alan 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 takas için geçici bir değer. Sayma sıralaması da aynı sınır değerlerine sahiptir, ancak diziyi iki kez okur.

Renkleri Sıralama için sayma sıralaması kabul edilebilir bir yanıt mı?

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. Ardından tek geçişte çözüm sunmanızın istenmesini bekleyin. Bölümleme yalnızca üç gruba ayırdığı için, çok sayıda renk olduğunda sayma daha iyi bir yöntemdir.

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

Test #1

Test #2

Test #3

Argüman

nums = [2, 1, 0, 2, 0, 1, 1]

Beklenen Çıktı

[0, 0, 1, 1, 1, 2, 2]

Sort Colors

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Elle balon sıralaması

Her rengi sayın, ardından yeniden yazın

Üç işaretçiyle tek geçiş (Hollanda ulusal bayrağı)

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler