Merge Sorted Array

Q: İki sıralı diziyi birleştirmenin zaman karmaşıklığı nedir?

İki işaretçiyle bu, O(m + n) olur; burada m ve n iki uzunluktur. Her adımda bir değer yerleştirilir ve hiçbir değere iki kez bakılmaz. Birleştirme ve sıralama ise O((m + n) log(m + n)) maliyetlidir.

Q: İki sıralı diziyi yerinde nasıl birleştirirsiniz?

İlk dizinin sonunda her ikisi için de yer varsa, onu sondan başlayarak doldur. İki dizinin kalan en büyük değerlerini karşılaştır, büyük olanı son boş konuma yaz ve sola ilerle. Sondan başlayarak yazmak, ilk dizinin henüz yerleştirilmemiş bir değerinin üzerine yazmaz; bu nedenle ikinci bir diziye gerek yoktur.

Q: İki sıralı diziyi birleştirmek, birleştirmeli sıralamanın birleştirme adımıyla aynı mıdır?

Evet. Birleştirme sıralaması diziyi ikiye böler, her yarıyı sıralar ve ardından bu iki sıralı yarıyı tam olarak bu iki işaretçili döngüyle birleştirir. Eşitlik durumunda soldaki değeri almak, eşit değerlerin özgün sıralarını korur; birleştirme sıralamasını kararlı yapan da budur.

Q: Neden dizileri birleştirip sort çağırmıyoruz?

Doğru yanıtı verir ve pratikte çoğu zaman hızlıdır. Ancak girdilerin zaten sıralanmış olduğunu göz ardı eder ve fazladan bir log çarpanına mal olur. Bir mülakatta beklenen yanıt, iki işaretçili birleştirmedir; çünkü bu, sana verilen sıralamadan yararlanabildiğini gösterir.

Kolayİki işaretçi Sıralama

+10

İki tamsayı dizisi veriliyor: nums1 ve nums2. Her biri zaten azalmayan sırada sıralanmıştır. Her iki dizideki tüm değerleri, yine azalmayan sırada içeren tek bir dizi döndürün. Her iki dizide de bulunan bir değer, toplamda kaç kez görünüyorsa sonuçta da o kadar kez yer alır.

Fonksiyon

merge(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: ilk sıralanmış dizi
nums2integer-array: ikinci sıralanmış dizi
Döndürürinteger-array: Her iki dizideki tüm değerleri, uzunluğu nums1.length + nums2.length olan tek bir sıralı dizide

Kısıtlar

1 ≤ nums1.length, nums2.length ≤ 2000
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 ve nums2 dizilerinin her biri azalmayan sırada sıralanmıştır.

Örnekler

Girdi: nums1 = [1, 4, 9]nums2 = [2, 3, 10]
Çıktı: [1, 2, 3, 4, 9, 10]
Açıklama: İki baştaki değeri oku ve küçük olanı tut: 1, ardından nums2 dizisinden 2 ve 3, sonra nums1 dizisinden 4 ve 9, en son da 10. Sonuç altı değerin tamamını içerir.

Girdi: nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
Çıktı: [-5, 0, 0, 0, 6, 8]
Açıklama: 0, nums1 içinde iki kez ve nums2 içinde bir kez göründüğü için sonuçta üç tane 0 vardır. -5, nums2 içindeki her şeyden küçüktür ve ilk sırada gelir.

Gönderirken +13 gizli test

Ek soru

k sıralı diziyi, toplamda N değer tutarken O(N log k) sürede birleştirebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Dizileri birleştirip sıralamak doğru cevabı verir, ancak her iki yarının da zaten sıralı olduğu gerçeğini göz ardı eder. Genel olarak geriye kalan en küçük değer her zaman iki diziden birinin başındadır. Her dizi için bir indeks tutun, her adımda baştaki küçük değeri alın ve tek bir geçişte sonucu oluşturun. Bu, birleştirmeli sıralamanın birleştirme adımıdır.

Birleştir ve sırala

Sezgi

nums1 içindeki her değeri ve nums2 içindeki her değeri tek bir diziye koyun, ardından sıralayın. Sonuç, her değeri göründüğü sayıda ve doğru sırada içerir.

[1, 4, 9] ve [2, 3, 10] için birleştirilmiş dizi [1, 4, 9, 2, 3, 10] olur ve sıralama sonucunda [1, 2, 3, 4, 9, 10] elde edilir.

nums1 içinde m değer ve nums2 içinde n değer olduğunda, genel bir sıralama O((m + n) log(m + n)) maliyetlidir. İşe yarar ve bu sınırlar için yeterince hızlıdır, ancak size verilen sıralı düzenden yararlanmaz. Sonraki yaklaşım bundan yararlanır ve log çarpanını ortadan kaldırır.

Algoritma

nums1 değerlerini, ardından nums2 değerlerini içeren bir dizi oluşturun.
Diziyi artan sayısal sırada sıralayın.
Diziyi döndürün.

def merge(nums1, nums2):
    return sorted(nums1 + nums2)

İki işaretçi, her dizi için bir tane

Sezgi

nums1 içinde i ve nums2 içinde j indekslerini tut; ikisi de 0'dan başlasın. i'den önceki ve j'den önceki her şey zaten sonuçta. Henüz kullanılmamış en küçük değer nums1[i] veya nums2[j]'dir; çünkü her dizi sıralıdır ve kalan değerleri yalnızca daha büyük olabilir. Küçük olanı ekle ve o indeksi ilerlet.

[1, 4, 9] ve [2, 3, 10] dizilerinde: 1, 2'den önce gelir; sonra 2, 4'ten; 3, 4'ten; 4, 10'dan; 9 da 10'dan önce gelir. Artık nums1 tükenmiştir, bu yüzden nums2'nin geri kalanı olan [10] olduğu gibi kopyalanır. Sonuç [1, 2, 3, 4, 9, 10] olur.

Her adımda bir değer yazılır, bu yüzden döngü m + n kez çalışır: O(m + n) zaman. Sonuç dizisi, kullanılan tek ek bellektir.

Algoritma

i ve j değerlerini 0 olarak ayarlayın ve boş bir sonuç oluşturun.
Her iki dizide de eleman kaldığı sürece nums1[i] ile nums2[j] değerlerini karşılaştırın.
Küçük olanı ekleyin ve indeksini ilerletin. Eşitlik durumunda nums1[i] değerini alın.
Bir dizi tükendiğinde diğer dizide kalanları ekleyin.
Sonucu döndürün.

def merge(nums1, nums2):
    result = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    # one array is used up; the rest of the other is already sorted
    result.extend(nums1[i:])
    result.extend(nums2[j:])
    return result

Tuzaklar ve uç durumlar

Çoğu hata, dizilerden biri tükendiğinde veya değerlerin karşılaştırılma biçiminde ortaya çıkar.

Dizilerden biri biter bitmez döngüyü durdurup diğer dizinin geri kalanını unutmak. [1, 2, 3] ve [4, 5, 6] için döngü 1, 2 ve 3'ten sonra biter; 4, 5, 6'nın da kopyalanması gerekir.
i sona ulaştıktan sonra nums1[i] değerini okumak. Karşılaştırma yapmadan önce her iki indeksi de kontrol et.
Yinelenen değerleri atlamak. [0, 0] ve [0], [0] değil, [0, 0, 0] olarak birleştirilir.
JavaScript ve TypeScript'te, karşılaştırıcı olmadan kullanılan sort() sayıları metin olarak sıralar; bu nedenle [-5, 10, 9], [-5, 10, 9] olarak sıralanır. (a, b) => a - b kullan.
Lua ve R'de diziler 1'den başladığı için her iki indeks de 1'den başlar ve sınır denetimlerinde <= kullanılır.

Sıkça sorulan sorular4

İki sıralı diziyi birleştirmenin zaman karmaşıklığı nedir?

İki işaretçiyle bu, O(m + n) olur; burada m ve n iki uzunluktur. Her adımda bir değer yerleştirilir ve hiçbir değere iki kez bakılmaz. Birleştirme ve sıralama ise O((m + n) log(m + n)) maliyetlidir.

İki sıralı diziyi yerinde nasıl birleştirirsiniz?

İlk dizinin sonunda her ikisi için de yer varsa, onu sondan başlayarak doldur. İki dizinin kalan en büyük değerlerini karşılaştır, büyük olanı son boş konuma yaz ve sola ilerle. Sondan başlayarak yazmak, ilk dizinin henüz yerleştirilmemiş bir değerinin üzerine yazmaz; bu nedenle ikinci bir diziye gerek yoktur.

İki sıralı diziyi birleştirmek, birleştirmeli sıralamanın birleştirme adımıyla aynı mıdır?

Evet. Birleştirme sıralaması diziyi ikiye böler, her yarıyı sıralar ve ardından bu iki sıralı yarıyı tam olarak bu iki işaretçili döngüyle birleştirir. Eşitlik durumunda soldaki değeri almak, eşit değerlerin özgün sıralarını korur; birleştirme sıralamasını kararlı yapan da budur.

Neden dizileri birleştirip sort çağırmıyoruz?

Doğru yanıtı verir ve pratikte çoğu zaman hızlıdır. Ancak girdilerin zaten sıralanmış olduğunu göz ardı eder ve fazladan bir log çarpanına mal olur. Bir mülakatta beklenen yanıt, iki işaretçili birleştirmedir; çünkü bu, sana verilen sıralamadan yararlanabildiğini gösterir.

Python

def merge(nums1, nums2):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums1 = [1, 4, 9]
nums2 = [2, 3, 10]

Beklenen

[1, 2, 3, 4, 9, 10]