Leetcode 4 Median of Two Sorted Arrays

Soru

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Örnek 1

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Örnek 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Çözüm

• “4. Median of Two Sorted Arrays” sorusu, iki sıralı diziden oluşan veri kümesinin medyanını bulmanızı ister. Bu problem, genellikle iki sıralı dizi verildiğinde bunların birleşiminden oluşan dizinin medyanını etkili bir şekilde hesaplamak için tasarlanmıştır. Problemde, dizilerin boş olmadığı ve birleşimlerinin en az bir eleman içerdiği belirtilir.
• Girdi: İki sıralı tam sayı dizisi nums1 ve nums2.
• Çıktı: İki dizinin birleşiminden oluşan dizinin medyanı.
• Bu problemi çözmek için kullanılan yaygın bir yöntem, iki sıralı dizide ikili arama (binary search) kullanmaktır. Temel fikir, bir dizi içinde medyanı bulmak için kullanılan ikili arama tekniğini iki diziye uygulamaktır. Bu yaklaşım, özellikle iki dizi birleştirildiğinde medyanın belirlenmesi gerektiğinde etkilidir.
• Çalışma Mekanizması:
• Dizileri Yeniden Sıralama ve İndeks Ayarlama: Daha kısa diziyi A, diğerini B olarak ayarla. Böylece arama süreci daha hızlı olur.
• İkili Arama Uygulama: A üzerinde ikili arama yaparak, her adımda B üzerinde de uygun bir indeks hesapla. Bu indeksler medyanı belirlemek için kullanılacak.
• Koşulların Kontrolü: A ve B üzerinde bulunan elemanlar arasında karşılaştırmalar yaparak, medyanın doğru yerde olup olmadığını kontrol et.
• Sonucun Hesaplanması: Medyanı hesapla. Eğer toplam uzunluk tek sayı ise, ortadaki değeri döndür. Çift sayı ise, ortadaki iki değerin ortalamasını al.

Code

def findMedianSortedArrays(nums1, nums2):
    # Kısa olan diziyi A, diğerini B olarak adlandır
    A, B = (nums1, nums2) if len(nums1) < len(nums2) else (nums2, nums1)
    total = len(A) + len(B)
    half = total // 2

    l, r = 0, len(A) - 1
    while True:
        i = (l + r) // 2  # A'da medyan için orta nokta
        j = half - i - 2  # B'de medyan için orta nokta

        Aleft = A[i] if i >= 0 else float("-infinity")  # Sınırları kontrol et
        Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
        Bleft = B[j] if j >= 0 else float("-infinity")
        Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")

        # Medyanı doğru bölgede bulduk
        if Aleft <= Bright and Bleft <= Aright:
            if total % 2:
                return min(Aright, Bright)
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
        elif Aleft > Bright:
            r = i - 1
        else:
            l = i + 1

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(log(min(m, n))), burada m ve n iki dizinin uzunluklarıdır. Daha kısa dizi üzerinde ikili arama yapılır.
• Space complexity (Alan Karmaşıklığı) : O(1), çünkü ekstra alan kullanılmaz.