Median of Two Sorted Arrays

Q: İki Sıralı Dizinin Medyanı'nın zaman karmaşıklığı nedir?

Kesim üzerindeki ikili arama O(log(min(m, n))) zaman ve O(1) alan alır; çünkü her adımda kısa listedeki olası kesimlerin sayısı yarıya iner. Birleştirme O(m + n) sürer: her biri 3000 öğeden oluşan iki liste için, 6000 öğeye karşı yaklaşık 12 adım.

Q: Daha kısa dizide neden ikili arama yapıyoruz?

Çünkü j = half-i . i daha kısa liste üzerinde ilerlerken j , 0 ile daha uzun listenin uzunluğu arasında kalır; böylece her okuma ya aralık içindedir ya da sonsuzluk olarak ele aldığın listenin sonunu aşar.

Zorİkili arama

+10

Sana iki tam sayı listesi veriliyor: nums1 ve nums2. Her biri küçükten büyüğe sıralıdır ve en az bir değer içerir. Tüm değerlerinin birlikte medyanını metin olarak döndür.

Toplam sayı adedi tekse medyan ortadaki değerdir; örneğin "4". Adet çiftse medyan ortadaki iki değerin ortalamasıdır; örneğin "2.5" veya "-0.5". Tam sayıları ondalık nokta olmadan, sıfırı ise "0" olarak yaz; asla "-0" yazma. O(log(min(m, n))) zaman karmaşıklığını hedefle.

Fonksiyon

findMedianSortedArrays(nums1: integer-array, nums2: integer-array) → string

nums1integer-array: en küçükten en büyüğe sıralanmış ilk liste
nums2integer-array: küçükten büyüğe sıralanmış ikinci liste
Döndürürstring: tüm değerlerin medyanı; "4" veya "-2.5" gibi metin olarak

Kısıtlar

1 ≤ nums1.length, nums2.length ≤ 3000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
Her iki liste de azalmayan sırada sıralanmıştır ve değerler tekrarlanabilir.

Örnekler

Girdi: nums1 = [1, 4]nums2 = [2, 7, 9]
Çıktı: "4"
Açıklama: Birlikte değerler 1, 2, 4, 7, 9'dur. Beş değer olduğundan bir orta değer vardır; üçüncü değer olan 4.

Ek soru

İki listenin k'ıncı en küçük değerini, herhangi bir k için logaritmik zamanda bulmak üzere aynı kesimi kullanabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Listeleri birleştirmek medyanı O(m + n) sürede verir, ancak okuduğu değerlerin çoğu yanıtı değiştiremez. Medyan yalnızca alt ve üst yarı arasındaki kesimin nerede olduğuna bağlıdır ve bu kesimi bir sayı belirler: alt yarının kısa listeden aldığı değerlerin sayısı. İkili arama bunu O(log(min(m, n))) adımda bulur.

İki listeyi birleştir

Sezgi

Listeleri merge sort'un yaptığı gibi birleştirerek sıralı tek bir liste elde edin: merged. total = m + n olduğunda, tam sayı bölmesi kullanarak merged[(total-1)/2] ile merged[total/2] değerlerini toplayın. Toplam tekse ikisi de ortadaki değerdir; çiftse ortadaki iki değerdir, dolayısıyla her iki durumda da toplamın yarısı medyandır.

Ortaya gelince dursanız bile birleştirme adımları değerlerin yarısının üzerinden geçer, bu nedenle zaman karmaşıklığı O(m + n) olur.

Algoritma

Listeleri merged içine birleştir; her zaman o anki daha küçük değeri, ardından geriye kalan listenin geri kalanını al.
total = m + n ile merged[(total-1)/2] ve merged[total/2] değerlerini topla.
Toplamın yarısını metin olarak döndür: çift bir toplamı 2'ye böl; tek bir toplam için işareti, mutlak değerinin yarısını ve .5 yaz.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Merge the two sorted lists into one, the way merge sort does.
    merged = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    merged.extend(nums1[i:])
    merged.extend(nums2[j:])
    total = len(merged)
    # For an odd total both indexes point at the one middle value.
    return half_text(merged[(total - 1) // 2] + merged[total // 2])

Kesme noktası üzerinde ikili arama

Sezgi

Alt yarının half = (m+n+1)/2 değer içermesini sağlayın; toplam tek olduğunda fazladan bir değer olur. nums1 dizisinin başından i değer, nums2 dizisinin başından ise j = half-i değer alır. Kesim, alt taraftaki hiçbir değer üst taraftaki herhangi bir değerden büyük olmadığında doğrudur. Her iki liste de sıralı olduğundan geriye iki kontrol kalır: left1 ≤ right2 ve left2 ≤ right1; burada left, bir listenin alt yarıya verdiği son değer, right ise listede kalan ilk değerdir. Eksik bir taraf eksi veya artı sonsuz kabul edilir.

left1 > right2 ise i çok büyüktür; left2 > right1 ise çok küçüktür. Dolayısıyla i, 0 ile m arasında ikili aramayla bulunur. [1, 2] ve [3, 4] üzerinde i = 1, left2 = 3 > right1 = 2 koşulunda başarısız olur; i = 2 ise başarılıdır: (2 + 3) / 2 = 2.5.

Algoritma

nums1'i daha kısa liste yap; half = (m+n+1)/2 olsun.
i için lo = 0 ile hi = m arasında ikili arama yap; j = half-i olsun.
left1 = nums1[i-1], right1 = nums1[i], left2 = nums2[j-1] ve right2 = nums2[j] değerlerini oku; bir dizinin sonunun ötesinde sonsuzluk kullan.
left1 > right2 ise hi = i-1 olarak ayarla. left2 > right1 ise lo = i+1 olarak ayarla.
Aksi takdirde, toplam eleman sayısı tekse max(left1, left2) değerini döndür. Çiftse, metin olarak max(left1, left2) + min(right1, right2) değerinin yarısını al.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Binary search over the shorter list.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2   # size of the left half; it gets the extra value when m + n is odd
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2    # values the left half takes from nums1
        j = half - i          # values it takes from nums2
        # An empty side counts as minus or plus infinity.
        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")
        if left1 > right2:
            hi = i - 1        # too many values from nums1
        elif left2 > right1:
            lo = i + 1        # too few values from nums1
        else:
            left_max = max(left1, left2)
            if (m + n) % 2 == 1:
                return str(left_max)
            return half_text(left_max + min(right1, right2))
    return ""  # not reached: sorted input always has a valid split

Tuzaklar ve uç durumlar

Kayan noktalı sayılarla ikiye bölme. Python, tam sayı olan bir medyanı 3.0 olarak yazdırır ve C'deki %f, 2.5 değerini 2.500000 olarak yazdırır. Toplamı tamsayı olarak tut.
Negatif tek bir toplam için tamsayı bölümünü ve .5 değerini yazmak. C ve Java'da -1 / 2 sonucu 0'dır; bu da -0.5 için 0.5 verir. Python'da -5 // 2 sonucu -3'tür; bu da -2.5 için -3.5 verir. Mutlak değeri ikiye böl ve işareti geri koy.
-0 yazmak. Ortadaki -1 ve 1 değerlerinin toplamı 0'dır ve yanıt "0" olur. İşareti toplamdan al.
Daha uzun listeyi aramak. j = half-i değeri 0'ın altına düşebilir veya n değerini aşabilir. Önce listelerin yerini değiştir.
i = 0 olduğunda, [9] ve [1, 2] örneklerinde olduğu gibi nums1[i-1] değerini okumak. Eksik değerler için sonsuzlukları kullan.

Sıkça sorulan sorular3

İki Sıralı Dizinin Medyanı'nın zaman karmaşıklığı nedir?

Kesim üzerindeki ikili arama O(log(min(m, n))) zaman ve O(1) alan alır; çünkü her adımda kısa listedeki olası kesimlerin sayısı yarıya iner. Birleştirme O(m + n) sürer: her biri 3000 öğeden oluşan iki liste için, 6000 öğeye karşı yaklaşık 12 adım.

Daha kısa dizide neden ikili arama yapıyoruz?

Çünkü j = half-i. i daha kısa liste üzerinde ilerlerken j, 0 ile daha uzun listenin uzunluğu arasında kalır; böylece her okuma ya aralık içindedir ya da sonsuzluk olarak ele aldığın listenin sonunu aşar.

Ondalık sayı kullanmadan medyanı nasıl döndürürsünüz?

İki orta değeri tam sayı olarak toplayın. Çift olan toplamı 2'ye bölün. Tek olan toplam için mutlak değerinin yarısını ve .5 yazın; toplam negatifse başına eksi işareti koyun: -1, "-0.5" olur.

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

Test #1

Test #2

Test #3

Argümanlar

nums1 = [1, 4]
nums2 = [2, 7, 9]

Beklenen Çıktı

"4"